Преобразование грамматики в LL(1)

У меня есть следующая грамматика:

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

С этим набором firstи follow:

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

Я создал следующую таблицу синтаксического анализа:

                $           =           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

Отсюда я вижу, что это не LL(1).

Как я могу изменить эту грамматику, чтобы она стала LL(1)?


parsing compiler-construction ll
person Favolas    schedule 08.06.2014    source источник
comment
Нет никакого систематического способа сделать это. Вам нужно пройти через все различные способы преобразования грамматик, описанные практически в любом учебнике по компиляторам. Этот ответ имеет довольно хороший обзор.   -  person John C    schedule 08.06.2014

Ответы (1)


arrow_upward
0
arrow_downward

Если вы думаете о том, какие типы строк могут быть сгенерированы этой конкретной грамматикой, это все строки одной из следующих форм:

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

Имея это в виду, вы можете спроектировать грамматику LL(1) для этого языка, по существу создав новую грамматику для языка с нуля. Вот один из способов сделать это:

Начальный оператор $

Выписка StarredID OptExpr

StarredID * StarredID | я бы

ОптЭкспр | = Помеченный ID

Здесь ПЕРВЫЕ наборы даны следующим образом:

  • ПЕРВЫЙ (Начало) = {*, идентификатор}
  • ПЕРВЫЙ (Утверждение) = {*, идентификатор}
  • ПЕРВЫЙ (StarredID) = {*, идентификатор}

  • ПЕРВЫЙ(ОптВыражение) = {, *, идентификатор}

  • СЛЕДУЙТЕ(Утверждение) = {$}

  • ПОДПИСАТЬСЯ(StarredID) = {=, $}
  • СЛЕДУЙТЕ(ОптВыражение) = {$}

Таблица синтаксического анализа показана здесь:

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

Итак, эта грамматика — LL(1).

person templatetypedef    schedule 16.03.2016