parsing - Transform grammar into LL(1)

Question

I have the following grammar:

START -> STM $
STM -> VAR = EXPR
STM -> EXPR
EXPR -> VAR
VAR -> id
VAR -> * EXPR

With this firstand follow sets:

          First set     Follow set
START       id, *       $
STM         id, *       $
EXPR        id, *       $, =
VAR         id, *       $, =

I've created the parsing table that follows:

                $           =           id              *               $
START                           START → STM $        START → STM $
STM                             STM → VAR = EXPR    STM → VAR = EXPR
                                STM → EXPR          STM → EXPR
EXPR                            EXPR → VAR          EXPR → VAR
VAR                             VAR → id            VAR → id
                                VAR → * EXPR        VAR → * EXPR

From here I can see that this is not LL(1).

How can I modify this grammar so that it becomes LL(1)?

Answer 1

如果您考虑这种特定语法可以生成哪些类型的字符串，它是以下形式之一的所有字符串：

 ***....**id
 ***....**id = ***...**id

考虑到这一点，您可以通过从头开始为该语言构建一个新语法来为该语言设计一个 LL(1) 语法。这是执行此操作的一种方法：

开始 → 声明 $

声明 → StarredID OptExpr

已加星标 ID → * 已加星标 ID | ID

OptExpr → ε | = 加星标ID

在这里，FIRST 集合如下：

• FIRST(开始) = {*, id}
• FIRST(语句) = {*, id}
• FIRST(StarredID) = {*, id}

• FIRST(OptExpr) = {ε, *, id}

• 跟随（语句）= {$}

• 关注（已加星标的 ID）= {=, $}
• 跟随(OptExpr) = {$}

然后在此处显示解析表：

                  *                 | id                | =             $
 ---------------+-------------------+-------------------+-------------+-----------
 Start          | Statement$        | Statement$        |             |
 Statement      | StarredID OptExpr | StarredID OptExpr |             |
 StarredID      | * StarredID       | id                |             |
 OptExpr        |                   |                   | = StarredID | epsilon

所以这个文法是LL(1)。