3

给定语法规则（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}

4

1 回答 1

2

这是一个使用Marpa::R2的快速而肮脏的脚本， Marpa的Perl接口，一个通用 BNF 解析器，用于使用您提供的语法及其修改版本解析输入，支持懒惰进食和左关联，但不t 禁止"a"： 代码，输出。

对于您提供的输入，语法并不模棱两可，否则parse()会引发异常。

希望这可以帮助。

PS在 Marpa 社区中讨论了使用 Marpa 的通用 BNF 解析功能为 TeX（以及其他）提供更好语法的前端。

更新：重新提问者的评论

此语法（在Marpa SLIF DSL中，|| 表示较低优先级）

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

明确解析问题中的输入 except "a+a"+"a+a"，"x"可能需要替代方案（这将使语法模棱两可，正如 rici 在下面的评论中有用地建议的那样，下一段中将对此进行更多说明）： code，output。

总体而言，使用双引号 " 作为括号，'+' 作为，另外，很容易为优先级低于 '+' 的操作添加符号，例如 '.' 用于连接并使其成为经典的术语/因子语法，在 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
于 2014-12-26T13:46:32.483 回答