给定语法规则(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
。应用:我不喜欢在LaTeX中转义
""a+a"+a"
和{
,所以我想制作一个只需要转义一个字符的LaTeX方言,例如用一个字符}
替换{
和}
,并编写类似"
而不是""1+2"/3"^"a+b"
的内容。 最佳答案
Here是一个快速而肮脏的脚本,它使用Marpa::R2,一个Perl接口来Marpa, a general BNF parser解析输入,使用您提供的语法及其修改后的版本,该版本支持延迟进食和左ASSOC,但不禁止"a"
:
code,output。
对于您提供的输入,语法并不含糊,因为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在下面的注释中所建议的,下一段将详细介绍):code,output。总的来说,使用双引号“作为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