如何证明左边递归语法不是在LL使用解析表（1） [英] How to prove left-recursive grammar is not in LL(1) using parsing table

问题描述

我有一个语法和想证明它是不是在LL（1）：

I have a grammar and would like to prove that it is not in LL(1):

S->SA|A
A->a

由于它是一个左递归grammarm，找到第一个，然后按照台我消除了左递归，得到：

As it is a left-recursive grammarm, to find the first and follow sets I eliminated the left recursion and got:

S->AS'
S'->AS'|Empty
A->a

first of A={a}      follow of S={$}
first of s'={a,ε}   follow of S'={$}
first of S={a}       follow of A={a,$}

但是，当我填写了分析表，我没跟2项得到任何细胞。然后一个人如何证明给定的语法不是在LL（1）？

But when I filled in the parsing table, I did not get any cell with 2 entries. Then how is one to prove that the given grammar is not in LL(1)?

推荐答案

首先你发现FIRST和FOLLOW在其中您已删除左递归语法。因此，当然，如果你尝试创建LL（1）分析表，不会有任何2项为左递归被删除，语法是明确的。

First of all you are finding FIRST and FOLLOW over the grammar in which you have removed left recursion. Therefore surely if you try to create LL(1) parsing table there won't be any 2 entries as left recursion is removed and grammar is unambiguous.

语法[S-> SA | A A-> A]是不是LL（1）左递归存在。要通过构建LL（1）分析表，你需要找到第一个也是唯一不修改它这个语法FOLLOW证明这一点。

Grammar[ S->SA|A A->a ] is not LL(1) as left recursion exists. To prove it by constructing LL(1) parsing table you need to find FIRST and FOLLOW on this grammar only without modifying it.

开始>一，给人FIRST（A）= {A}

Start from bottom A->a , gives FIRST(A)={a}

S-> A，给人FIRST（S）= FIRST（A）= {A}

S->A , gives FIRST(S)=FIRST(A)={a}

S-> SA，给人FIRST（S）= FIRST（S），我觉得问题就出现在这里。在这样的递归调用规则说计算FIRST（S），直到它的变化，即直到元素被首先添加（S）继续计算。一旦停止变化就是你的答案

S->SA , gives FIRST(S)=FIRST(S) , I think problem arises here. In such recursive calls rules says calculate FIRST(S) till it changes i.e. until elements are added in FIRST(S) continue to calculate. Once it stops changing that is you answer

因此​​第一（S）= FIRST（S）= {A}，调用第一（S），为多次可能也不会发生变化。
分析表：

Therefore FIRST(S)=FIRST(S)={a} , you call FIRST(S) as many times possible it won't change. Parsing Table:

      a
------------ 
S   S->SA
    S->A
-------------
A   A->a 

因此​​，有两个条目（S，a）中。因此不LL（1）

So there are two entries for (S,a). Thus it is not LL(1)

这篇关于如何证明左边递归语法不是在LL使用解析表（1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！