给定语法规则(BNF,|表示或):

x := a | x x | x + x | x + "x" | "x" + x | "x" + "x"

,与
+左联想(a+a+a表示(a+a)+a),
级联左关联(aaa表示(aa)a,而不是a(aa)),
懒散地吃操作对象(意味着)。
问题:这个语法有歧义吗也就是说,可以用两种不同的方式解析字符串吗?
示例:
允许:+aa+aaa(a+a)aa(读作a+a),a+"a"(读作"a+a"+"a+a"),(a+a)+(a+a)""a"+"a""+"a"((a)+(a))+(a)
禁止:a+a+aa+"a"+a"a+a"+"a"a++a"a"a+"a
应用:我不喜欢在LaTeX中转义""a+a"+a"{,所以我想制作一个只需要转义一个字符的LaTeX方言,例如用一个字符}替换{},并编写类似"而不是""1+2"/3"^"a+b"的内容。

最佳答案

Here是一个快速而肮脏的脚本,它使用Marpa::R2,一个Perl接口来Marpa, a general BNF parser解析输入,使用您提供的语法及其修改后的版本,该版本支持延迟进食和左ASSOC,但不禁止"a"
codeoutput
对于您提供的输入,语法并不含糊,因为parse()会抛出异常。
希望这有帮助。
p.s.使用marpa的通用bnf解析功能,为tex提供一个具有更好语法的前端(除其他外)was discussed in the Marpa community
更新:重新询问的评论
此语法(在Marpa SLIF DSL中,表示较低的优先级)

x ::= a
   ||    x     '+'     x
   |     x     '+' '"' x '"'
   | '"' x '"' '+'     x
   | '"' x '"' '+' '"' x '"'
   ||    x             x

毫不含糊地解析问题中的输入,除了"a+a"+"a+a",这需要"x"替代方法(这将使语法变得模棱两可,正如rici在下面的注释中所建议的,下一段将详细介绍):codeoutput
总的来说,使用双引号“作为paren,”+“以及,plus,很容易为优先级比“+”低的op添加一个符号,例如“用于连接”,并使其成为一个经典的术语/因子语法,可以在marpa slif dsl中表示如下:
x ::= a
  || '"' x '"' assoc => group
  || x '+' x
  || x '.' x

更新1:
# input: "a+a"+"a+a"
Setting trace_terminals option
Lexer "L0" accepted lexeme L1c1 e1: '"'; value="""
Lexer "L0" accepted lexeme L1c1 e1: '"'; value="""
Lexer "L0" accepted lexeme L1c2 e2: a; value="a"
Lexer "L0" accepted lexeme L1c3 e3: '+'; value="+"
Lexer "L0" accepted lexeme L1c3 e3: '+'; value="+"
Lexer "L0" accepted lexeme L1c4 e4: a; value="a"
Lexer "L0" accepted lexeme L1c5 e5: '"'; value="""
Lexer "L0" accepted lexeme L1c5 e5: '"'; value="""
Lexer "L0" accepted lexeme L1c6 e6: '+'; value="+"
Lexer "L0" accepted lexeme L1c6 e6: '+'; value="+"
Lexer "L0" accepted lexeme L1c7 e7: '"'; value="""
Lexer "L0" accepted lexeme L1c8 e8: a; value="a"
Error in SLIF parse: No lexeme found at line 1, column 9
* String before error: "a+a"+"a
* The error was at line 1, column 9, and at character 0x002b '+', ...
* here: +a"
Marpa::R2 exception at C:\cygwin\home\Ruslan\Marpa-R2-work\q27655176.t line 63.

Progress report is:
F3 @7-8 L1c7-8 x -> a .
R7:6 @0-8 L1c1-8 x -> '"' x '"' '+' '"' x . '"'
# ast dump:
undef

09-27 09:09