给定语法规则(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}
。
最佳答案
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
关于algorithm - 单字符括号匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27655176/