1

我已经在 bison 中制作了一个完整的解析器（当然还有在 flex 中完成的词法分析器），我昨天才注意到我的解析器有问题。实际上在If结构中。

这是我在解析器中的规则：http: //pastebin.com/TneESwUx

此处无法识别单个 IF，如果我将“%prec IFX”替换为“END”，则通过添加新标记“END”（"end" return END;在 flex 中），它可以工作。但我不想有一个新的“end”关键字，这就是我不使用这个解决方案的原因。

请帮我。

4

2 回答 2

2

'The correct way to handle this kind of rule is not precedence, it is refactoring to use an optional else-part so that the parser can use token lookahead to decide how to parse. I would design it something like this:

stmt      : IF '(' expression ')' stmts else_part
          | /* other statement productions here */

else_part : /* optional */
          | ELSE stmts

stmts     : stmt
          | '{' stmt_list '}'
          | '{' '}'

stmt_list : stmt
          | stmt_list ';' stmt

(This method of special-casing stmts instead of allowing stmt to include a block may not be optimal in terms of productions, and may introduce oddities in your language, but without more details it's hard to say for certain. bison can produce a report showing you how the parser it generated works; you may want to study it. Also beware of unexpected shift/reduce conflicts and especially of any reduce/reduce conflicts.)

Note that shift/reduce conflicts are entirely normal in this kind of grammar; the point of an LALR(1) parser is to use these conflicts as a feature, looking ahead by a single token to resolve the conflict. They are reported specifically so that you can more easily detect the ones you don't want, that you introduce by incorrectly factoring your grammar.

Your IfExpression also needs to be refactored to match; the trick is that else_part should produce a conditional expression of some kind to $$, and in the production for IF you test $6 (corresponding to else_part) and invoke the appropriate IfExpression constructor.

于 2012-05-13T18:34:22.457 回答
1

您的语法模棱两可，因此您必须忍受 shift/reduce 冲突。记号通过END确保IF语句始终正确闭合来消除歧义，就像一对括号一样。

括号在这里做了一个很好的类比。假设你有这样的语法：

maybe_closed_parens : '(' stuff
                    | '(' stuff ')'
                    ;

stuff本身会产生一些语法符号，其中之一是maybe_closed_parens.

因此，如果您输入 like ((((((whatever，那是正确的。括号不必闭合。但是，如果添加)呢？哪个(关门了？

这很像无法分辨哪个IF匹配ELSE.

如果您添加END到IF（无论是否有ELSE）的语法，那么这就像有一个右括号。IF和和END一样。()

当然，从风格上来说，你不想END在你的语言中使用这个词是正确的，因为你已经有了花括号块，它们基本上是 Pascal'sBEGIN和END. 你}已经是一个END关键字。

所以你可以做的是强加一个IF只接受复合语句的规则（即完全支撑）：

if_statement : IF condition compound_statement
             | IF condition compound_statement ELSE compound_statement

现在不可能有​​像 if x if yw else z 这样的歧义，因为大括号必须存在：if x { if y { w } else { z } } or if x { if y { w } } else { z }。

我似乎记得 Perl 是做出这种选择的语言的一个例子。这不是一个坏主意，因为它不仅消除了您的歧义，更重要的是它消除了程序中的歧义。

我看到您的语法中没有compound_statement短语结构规则，因为您的语句会直接生成一个包含在其中的{短语}。如果你采用这种方法，你将不得不破解它。

于 2012-05-14T00:01:36.560 回答