如何消除以下语法中的歧义? [英] How to remove ambiguity in the following grammar?

问题描述

如何消除后续语法中的歧义?

How to remove ambiguity in following grammar?

E -> E * F | F + E | F

F -> F - F | id

推荐答案

首先，我们需要找到歧义.

First, we need to find the ambiguity.

考虑不带F的E的规则；将F更改为f，并将其视为终端符号.然后是语法

Consider the rules for E without F; change F to f and consider it a terminal symbol. Then the grammar

E -> E * f
E -> f + E
E -> f

是模棱两可的.考虑f + f * f:

is ambiguous. Consider f + f * f:

    E                      E
    |                      |
    +-------+--+           +-+-+
    |       |  |           | | |
    E       *  f           f + E
  +-+-+                        |
  | | |                        +-+-+
  f + E                        E * f
      |                        |
      f                        f

我们可以通过强制*或+优先解决这种歧义.通常，*按操作顺序优先，但这完全是任意的.

We can resolve this ambiguity by forcing * or + to take precedence. Typically, * takes precedence in the order of operations, but this is totally arbitrary.

E -> f + E | A
A -> A * f | f

现在，字符串f + f * f只有一个解析:

Now, the string f + f * f has just one parsing:

    E
    |
    +-+-+
    | | |
    f + E
        |
        A
        |
        +-+-+
        A * f
        |
        f

现在，请考虑使用F而不是f的原始语法:

Now, consider our original grammar which uses F instead of f:

E -> F + E | A
A -> A * F | F
F -> F - F | id

这是模棱两可的吗?它是.考虑字符串id-id-id.

Is this ambiguous? It is. Consider the string id - id - id.

E                    E
|                    |
A                    A
|                    |
F                    F
|                    |
+-----+----+----+    +----+----+----+
      |    |    |         |    |    |
      F    -    F         F    -    F
      |         |         |         |
    +-+-+       id        id      +-+-+
    F - F                         F - F
    |   |                         |   |
    id  id                        id  id

这里的歧义是-可以是左关联的或右关联的.我们可以选择与+相同的约定:

The ambiguity here is that - can be left-associative or right-associative. We can choose the same convention as for +:

E -> F + E | A
A -> A * F | F
F -> id - F | id

现在，我们只有一个解析:

Now, we have only one parsing:

E
|
A
|
F
|
+----+----+----+
     |    |    |
     id   -    F
               |
            +--+-+
            |  | |
            id - F
                 |
                 id

现在，这个语法是否模棱两可?不是.

Now, is this grammar ambiguous? It is not.

• 中将有#(+)+ s，我们总是需要使用生产E-> F + E精确地#(+)次，然后使用生产E-> A一次.
• 中将有#(*)* s，我们总是需要使用生产A-> A * F精确地#(*)次，然后使用生产E-> F一次.
• 中将有#(-)-s，我们总是需要使用生产F-> id-F精确地#(-)次，生产F-> id一次.

那个s恰好具有#(+)+ s，#(*)* s和#(-)-s是理所当然的(如果s中不存在，则数字可以为零). E-> A，A-> F和F-> id必须只使用一次，可以显示如下:

That s has exactly #(+) +s, #(*) *s and #(-) -s can be taken for granted (the numbers can be zero if not present in s). That E -> A, A -> F and F -> id have to be used exactly once can be shown as follows:

如果从不使用E-> A，则派生的任何字符串中仍将包含E(一个非终结符)，因此该语言也不是字符串(不带E-> A至少不会生成任何东西) .另外，在使用E-> A之前可以生成的每个字符串中最多包含一个E(您以一个E开头，而其他生产中都保留一个E)，因此永远不可能使用E-> A大于一次.因此，E-> A仅对所有派生字符串使用一次.该演示对A-> F和F-> id的工作方式相同.

If E -> A is never used, any string derived will still have E, a nonterminal, in it, and so will not be a string in the language (nothing is generated without taking E -> A at least once). Also, every string that can be generated before using E -> A has at most one E in it (you start with one E, and the only other production keeps one E) so it is never possible to use E -> A more than once. So E -> A is used exactly once for all derived strings. The demonstration works the same way for A -> F and F -> id.

E-> F + E，A-> A * F和F-> id-F分别精确地使用了#(+)，#(*)和#(-)次.这些是唯一带有各自符号的作品，每个作品都带有一个实例.

That E -> F + E, A -> A * F and F -> id - F are used exactly #(+), #(*) and #(-) times, respectively, is apparent from the fact that these are the only productions that introduce their respective symbols and each introduces one instance.

如果考虑生成的语法的子语法，我们可以证明它们是明确的，如下所示:

If you consider the sub-grammars of our resulting grammars, we can prove they are unambiguous as follows:

F -> id - F | id

这是(id - )*id的明确语法. (id - )^kid的唯一派生是使用F -> id - F k次，然后仅使用F -> id一次.

This is an unambiguous grammar for (id - )*id. The only derivation of (id - )^kid is to use F -> id - F k times and then use F -> id exactly once.

A -> A * F | F

我们已经看到F对于它所识别的语言而言是明确的.通过相同的论点，这对于语言F( * F)*来说是明确的语法.推导F( * F)^k要求准确地使用A -> A * F k次，然后使用A -> F.因为从F生成的语言是明确的，并且因为A的语言使用*来明确区分F的实例，所以*并不是语法F生成的符号

We have already seen that F is unambiguous for the language it recognizes. By the same argument, this is an unambiguous grammar for the language F( * F)*. The derivation of F( * F)^k will require the use of A -> A * F exactly k times and then the use of A -> F. Because the language generated from F is unambiguous and because the language for A unambiguously separates instances of F using *, a symbol not generated by F, the grammar

A -> A * F | F
F -> id - F | id

也毫不含糊.要完成该论点，请将相同的逻辑应用于从起始符号E生成(F +)* A的语法.

Is also unambiguous. To complete the argument, apply the same logic to the grammar generating (F + )*A from the start symbol E.

这篇关于如何消除以下语法中的歧义?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！