制作语法LL(1) [英] Making a Grammar LL(1)

问题描述

我有以下语法:

S→a S b S | b S a S | ε

S → a S b S | b S a S | ε

由于我正在尝试为其编写一个小型编译器，所以我希望使其成为LL(1).我看到这里似乎有一个FIRST/FOLLOW冲突，而且我知道我必须使用替代来解决它，但是我不确定该如何解决.这是我建议的语法，但是我不确定它是否正确:

Since I'm trying to write a small compiler for it, I'd like to make it LL(1). I see that there seems to be a FIRST/FOLLOW conflict here, and I know I have to use substitution to resolve it, but I'm not exactly sure how to go about it. Here is my proposed grammar, but I'm not sure if it's correct:

S-> aSbT | epsilon

S-> aSbT | epsilon

T-> bFaF | epsilon

T-> bFaF| epsilon

F-> epsilon

F-> epsilon

有人可以帮忙吗?

推荐答案

在他的有关LR解析的原始论文，Knuth给出了该语言的以下语法，他猜想是该语言最简短的语法:"

In his original paper on LR parsing, Knuth gives the following grammar for this language, which he conjectures "is the briefest possible unambiguous grammar for this language:"

S→ ε |抗体bBaS

S → ε | aAbS | bBaS

A→ ε |抗体

A → ε | aAbA

B→ ε | bBaB

B → ε | bBaB

从直觉上讲，这试图将As和Bs的任何字符串分解为完全平衡的块.一些块以a开头并以b结束，而其他块以b开头并以a结束.

Intuitively, this tries to break up any string of As and Bs into blocks that balance out completely. Some blocks start with a and end with b, while others start with b and end with a.

我们可以如下计算FIRST和FOLLOW集:

We can compute FIRST and FOLLOW sets as follows:

FIRST(S)= {&epsilon ;, a，b}

FIRST(S) = { ε, a, b }

FIRST(A)= {&epsilon ;，一个

FIRST(A) = { ε, a }

FIRST(B)= {&epsilon ;, b}

FIRST(B) = { ε, b }

关注(S)= {$}

FOLLOW(S) = { $ }

FOLLOW(A)= {b}

FOLLOW(A) = { b }

FOLLOW(B)= {a}

FOLLOW(B) = { a }

基于此，我们获得以下LL(1)解析表:

Based on this, we get the following LL(1) parse table:

   |   a   |   b   |   $   
 --+-------+-------+-------
 S | aAbS  | bBaS  |  e
 A | aAbA  |   e   |
 B |   e   | bBaB  |

所以这个语法不仅是LR(1)，而且是LL(1).

And so this grammar is not only LR(1), but it's LL(1) as well.

希望这会有所帮助！

这篇关于制作语法LL(1)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！