如何证明语法不明确？ - （S）| SS |（） [英] How to Prove a Grammar is ambiguous? S -> (S)|SS|()

问题描述

我对语法比较陌生，想知道是否有人可以使用解析树帮助我确定下面的语法有多歧义？我知道它需要创建两个不同的字符串。

I am rather new to grammars, and was wondering if someone could help me determine using a parse tree how this grammar below is ambiguous? I know that it needs to have two different strings that can be created.

S -> (S)|SS|()

我可以将其默认转换为chomsky正常形式和greibach，但是

I can def convert it to chomsky normal form and greibach, but ambiguity is perplexing to me with these.

推荐答案

证明语法歧义的最简单方法是找到带有两个不同解析的句子树木。 （或者两个最右边的导数，这是完全相同的东西。或者，如果您愿意，两个不同的最左边的导数。）

The easiest way to prove a grammar ambiguous is to find a sentence with two different parse trees. (Or two different rightmost derivations, which is exactly the same thing. Or, if you prefer, two different leftmost derivations.)

S→ S S | X 始终是模棱两可的（对于任何 X ），因为句子 XXX 有两个不同的句子解析树：

S → S S | X is always ambiguous (for any X), because the sentence X X X has two different parse trees:

     S            S
    / \          / \
   /   S        S   \
  /   / \      / \   \
 X   X   X    X   X   X

这篇关于如何证明语法不明确？ - （S）| SS |（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！