解析上下文树免费语法 [英] Parse Tree Of Context Free Grammar

问题描述

我正在尝试找出如何正确解析树以显示语法是否模棱两可的方法.

I'm trying to figure out how to do parse trees correctly to show whether a grammar is ambiguous or not.

我的语法是S-> xSy | ySx | SS | e

my grammar is S -> xSy | ySx | SS | e

任何帮助都会很棒.预先感谢

any help would be great. thanks in advance

下面是我的裂缝...

below is my crack at it...

     S
    / \
   /   \
  x     y
 / \   / \
x   x  y  y

推荐答案

作为提示，几乎所有带有形式产生形式的语法

As a hint, pretty much any grammar with a production of the form

S→ SS

S → SS

将会是模棱两可的，因为如果您想产生三个S非末端，则可以通过两种方式进行:

will be ambiguous, because if you want to produce three S nonterminals you can do so in two ways:

      S                S
     / \              / \
    S   S            S   S
       / \          / \
      S   S        S   S

假设那些S实际上可以产生终端字符串，则可以将这两个小工具"放入解析树中，以两种不同的方式派生相同的字符串.

Assuming those S's can actually produce strings of terminals, these two "gadgets" can be put into the parse tree to derive the same string in two different ways.

希望这会有所帮助！

这篇关于解析上下文树免费语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！