Предиктивный синтаксический анализ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Общая схема построения парсеров с помощью FIRST и FOLLOW)
Строка 17: Строка 17:
 
     res = Node("A")
 
     res = Node("A")
 
     switch (curToken) :
 
     switch (curToken) :
        for \alpha_1, \alpha_2 .. \alpha_k
+
          case : <tex>FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1))  ?  FOLLOW(A)  :  \varnothing)</tex> :
            case : <tex>FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1))  ?  FOLLOW(A)  :  \varnothing)</tex> :
+
            // \alpha_1 = x_1x_2..x_{t_1}
                // \alpha_1 = X_1x_2..x_{t_1}
+
            for x_1 .. x_{t_1}
                // X_1 {{---}} нетерминал
+
                 if x_1 is terminal
                 Node t = X_1()
+
                    consume(x_1)
                res.addChild(t)
+
                    res.addChild(new Node("x_1")
                // x_2 {{---}} терминал
+
                    nextToken()
                consume(x_2)
+
                else
                res.addChild(new Node("x_2")
+
                    Node t = X_1()
                nextToken()
+
                    res.addChild(t)
                // x_3
+
            break
                ...
+
        case <tex>FIRST(\alpha_2) \cup ((\varepsilon \in FIRST(\alpha_2)) ?  FOLLOW(A) :  \varnothing)</tex> :
                break;
+
            ...
 +
            break
 +
        ...
 
         default :
 
         default :
 
             error("unexpected char")
 
             error("unexpected char")

Версия 16:21, 24 мая 2015

Эта статья находится в разработке!

Общая схема построения парсеров с помощью FIRST и FOLLOW

Для LL(1) грамматик возможна автоматическая генерация парсеров, если известны множества FIRST и FOLLOW. Существуют общедоступные генераторы: ANTLR, GNU bison, Yacc.

Пусть [math]\Gamma[/math] — LL(1)-грамматика. Построим для нее парсер.

Для каждого нетерминала A : [math]A \rightarrow \alpha_1 \mid \alpha_2 \mid ... \mid \alpha_k [/math] создадим функцию A() : Node, возвращающую фрагмент дерева разбора, выведенный из нетерминала A.

Здесь Node — структура вида:

Node
    children : list<Node>
    value : string

Тут картинка про строку.

A() : Node
    res = Node("A")
    switch (curToken) :
         case : [math]FIRST(\alpha_1) \cup ((\varepsilon \in FIRST(\alpha_1))  ?  FOLLOW(A)  :  \varnothing)[/math] :
            // \alpha_1 = x_1x_2..x_{t_1}
            for x_1 .. x_{t_1}
                if x_1 is terminal
                    consume(x_1)
                    res.addChild(new Node("x_1")
                    nextToken()
                else
                    Node t = X_1()
                    res.addChild(t)
            break
        case [math]FIRST(\alpha_2) \cup ((\varepsilon \in FIRST(\alpha_2))  ?  FOLLOW(A)  :  \varnothing)[/math] : 
            ...
            break
        ...
        default :
            error("unexpected char")
    return res
consume(char c) 
    if (curToken != c)
        error("expected" + c)
    nextToken()

Пример

Рассмотрим построение парсера на примере грамматики арифметических выражений. Запишем грамматику.

[math] E \to T + E \mid T \\ T \to F \times T \mid F \\ F \to n \mid (E) [/math]

Данная грамматика не является LL(1)-грамматикой, так как содержит правое ветвление, от него нужно избавиться перед построением парсера:

[math] E \to TE' \\ E' \to +TE' \mid \varepsilon \\ T \to FT' \\ T' \to \times FT' \mid \varepsilon \\ F \to n \mid (E) [/math]

Теперь грамматика стала LL(1)-грамматикой, построим для нее множества FIRST и FOLLOW (их построение подробно разобрано здесь).

Правило FIRST FOLLOW
[math]E[/math] [math]\{\ n,\ (\ \} [/math] [math]\{\ \$,\ )\ \} [/math]
[math]E'[/math] [math]\{\ +,\ \varepsilon\ \} [/math] [math]\{\ \$,\ )\ \} [/math]
[math]T[/math] [math]\{\ n,\ (\ \} [/math] [math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]T'[/math] [math]\{\ \times,\ \varepsilon\ \} [/math] [math]\{\ +,\ \$\ ,\ )\ \}[/math]
[math]F[/math] [math]\{\ n,\ (\ \} [/math] [math]\{\ \times, \ +,\ \$\ ,\ )\ \} [/math]

Построим функции обработки некоторых нетерминалов.

E()
    res = Node("E")
    switch(curToken)
        case 'n', '(' :
            res.addChild(T())
            res.addChild(E'())
            break
        default :
            error("unexpected char")
    return res
E'()
    res = Node("E'")
    switch(curToken) 
        case '+' :
            consume('+')
            res.addChild(Node("+"))
            res.addChild(T())
            res.addChild(E'())
            break
        case '$', ')' :
            break
        default :
            error("unexpected char")
     return res
F()
    res = Node("F")
    switch(curToken)
        case 'n' :
            consume('n')
            res.addChild(Node("n"))
            break
        case '(' :
            consume('(')
            res.addChild(Node("("))
            res.addChild(E())
            consume(')')
            res.addChild(Node(")"))
        default :
            error("unexpected char")
    return res

Функции для T и T' строятся аналогично.


TODO: Картинки примеров разбора чего-нибудь типа 1+2*3

TODO: Построение таблицы предиктивного анализа