algorithm - 单字符括号匹配

Question

给定语法规则(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+aa 表示 a(a+a)a)。

问题: 这个语法有歧义吗？ 即是否可以用两种不同的方式解析一个字符串？

示例:

允许:a, a+a, a+"a", "a+a"+"a+a "(读作 (a+a)+(a+a))，""a"+"a""+"a"(读作如 ((a)+(a))+(a)), a+a+a, a+"a"+a。

禁止:"a+a", +"a", a++a, "a"，a+"a，""a+a"+a"。

应用: 我讨厌在 LaTeX 中转义 { 和 }，所以我想做一个 LaTeX只需要转义一个字符的方言，因此将 { 和 } 都替换为一个字符 " 例如，这样写 ""1+2"/3"^"a+b" 而不是 {\frac{1+2}{3}}^{a+b}。

Answer 1

Here是一个使用 Marpa::R2 的快速而肮脏的脚本, 一个 Perl Marpa, a general BNF parser 的接口(interface)使用您提供的语法及其修改版本解析输入，支持懒惰进食和 left assoc，但不禁止 "a": code , output .

对于您作为 parse() 提供的输入，语法没有歧义。否则会抛出异常。

希望这对您有所帮助。

附言使用 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 在下面的评论中有用地建议的那样，在下一段中有更多关于):code , output .

总的来说，用双引号 "作为括号，'+' as, well, plus，很容易为优先级低于 '+' 的操作添加符号，例如 '.'用于连接并使其成为经典的术语/因子语法，在 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