BNF语法的歧义性

Question

BNF语法的歧义性

7

我最近在思考以下BNF

A -> x | yA | yAzA

where x,y,z are terminals.

我相信这个语法是有歧义的，但如何使它变得清晰明了？

- Mark Kennedy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Josh Haberman · Accepted Answer

如果一个特定的字符串可以有多个解析树，则语法是含糊不清的。在您的语言中，字符串yyxzx可以有以下两个解析树：

    A                  A
   / \                /|\`\
  y   A              y A z A
     /|\`\            / \   \
    y A z A          y   A   x
      |   |              |
      x   x              x

因此，语法是有歧义的。

实际上，这相当于类C语言中臭名昭著的“if/then/else”歧义问题，其中y=if，z=else，x=statement。http://en.wikipedia.org/wiki/Dangling_else。我建议查看该页面以获取解决此问题的想法。