0

最近我在学习解析表达式语法。在网上搜索了一些关于它的资料后，我终于坐下来弄脏了手。我想用 PEG 实现 Kernighan 和 Pike 的 The Unix Programming Environment 中的 hoc 程序。就此而言，我选择了 PEG 解析器生成器peg/leg，因为它具有良好的文档和大量示例。我以示例中的 dc.peg 作为起点，并在 phoc 版本 1 中实现了对一元减号的支持。

现在，当我为一元减去以下产生式时，生成的解析器无法识别 ((-9)), ((-9)*3)/4, (8-(-2)*5)/2-(2+ 2）等。

Operand     <-    SGNValue
                  / Value
SGNValue    <-    OPEN? '-' Value CLOSE?
Value       <-    NUMBER                                     
                  / OPEN Sum CLOSE

但是，如果我将 SGNValue 更改为以下表达式，则这些表达式完全匹配。

SGNValue    <-    '-' NUMBER                                        
                  / '-' OPEN Sum CLOSE

有人可以向我解释上述生产规则有什么问题吗？

我还在这篇文章中附加了 phoc1.peg 文件。

感谢和问候桑塔努

# Grammar

Expr        <-    SPACE Sum EOL                                      { printf("%f\n", pop()); }
                  / (!(EOL / 'q') .)* EOL                            { printf("error: quiting hoc1\n"); \
                                                                   exit(1); }
                  / 'q' EOL                                          { printf("bye\n"); exit(0);}

Sum         <-    Product ( PLUS  Product                            { double r = pop(), l = pop(); \
                                                                   push(l + r); }
                  / MINUS Product                                    { double r = pop(), l = pop(); \
                                                                   push(l - r); }
                  )*

Product     <-    Operand ( TIMES  Operand                           { double r = pop(), l = pop(); \
                                                                   push(l * r); }
                  / DIVIDE Operand                                   { double r = pop(), l = pop(); \
                                                                   push(l / r); }
                  )*

Operand     <-    SGNValue
                  / Value

## SGNValue    <-    OPEN? '-' Value CLOSE?
## This production rule was throwing error
## for expressions like ((-9)), ((-9)*3)/4,
## (8-(-2)*5)/2-(2+2), etc. probably due to
## left recurssion. But it was behaving as expected
## for (((9))), ((9)*2), etc.

SGNValue    <-    '-' NUMBER                                         { push(-1*atof(yytext)); }
                  / '-' OPEN Sum CLOSE                               { double d = pop(); push(-1*d); }

Value       <-    NUMBER                                             { push(atof(yytext)); }
                  / OPEN Sum CLOSE

# Lexemes

NUMBER  <-  < [0-9]+ ('.' [0-9]+)? >  SPACE
PLUS    <-  '+'                       SPACE
MINUS   <-  '-'                       SPACE
TIMES   <-  '*'                       SPACE
DIVIDE  <-  '/'                       SPACE
OPEN    <-  '('                       SPACE
CLOSE   <-  ')'                       SPACE
SPACE   <-  [ \t]*
EOL     <-  '\n' / '\r\n' / '\r'
4

1 回答 1

3

当你写：

SGNValue    <-    OPEN? '-' Value CLOSE?

您是说 theOPEN和 theCLOSE都是可选的，这意味着其中一个或两者都可能存在。它会很高兴地匹配，例如，-9)只有OPEN缺少 的地方。

所以前缀((-9匹配VALUE <- OPEN Sum CLOSE离开(-9匹配SUM，递归到OPERAND匹配VALUE / SGNValue；请记住，PEG 的/运算符是顺序感知的，因此它首先尝试VALUE再次匹配(and 递归。然后我们有-9which can't matchVALUE但它肯定可以 match SGNValue。不幸的是，如上所述， -9)matches之后没有足够的右括号来匹配来自两个s 的未决开括号。SGNValueVALUE

我不是 PEG 的忠实拥护者，订单感知交替是原因之一。但这是非常个人的观点；如果他们为你工作，你就会有更多的权力。OPEN? Sum CLOSE?在任何 BNF 风格的语法形式中都是不正确的，但通常它会导致接受错误的句子而不是拒绝正确的句子。

于 2014-05-31T04:40:15.033 回答