Как адаптировать этот анализатор LL (1) к парсеру LL (k)?

Question

В приложениях книги драконов в качестве примера приведен пример передней части LL (1). Я думаю, что это очень полезно. Тем не менее, я выясню, что для контекстной свободной грамматики ниже вместо этого нужен был, по крайней мере, LL (2) парсер.

statement : variable ':=' expression 
      | functionCall 

functionCall : ID'(' (expression (',' expression)*)? ')' 
      ; 
variable : ID 
     | ID'.'variable 
     | ID '[' expression ']' 
     ; 

Как я могу приспособить лексер для анализатора LL (1), чтобы поддерживать k, смотреть вперед жетоны? Есть ли какие-то изящные способы?

Я знаю, что могу добавить несколько буферов для токенов. Я хотел бы обсудить некоторые детали программирования.

---

это Parser:

class Parser 
{ 
    private Lexer lex; 
    private Token look; 
    public Parser(Lexer l) 
    { 
     lex = l; 
     move(); 
    } 

    private void move() 
    { 
     look = lex.scan(); 
    } 
} 

---

и Lexer.scan() возвращает следующую лексему из потока.

Answer 1

На самом деле вам нужно буферизировать k lookahead tokens, чтобы сделать LL(k) синтаксический анализ. Если k равно 2, вам просто нужно расширить свой текущий метод, который буферизует один токен в look, используя другой частный член look2 или некоторые такие. Для больших k вы можете использовать кольцевой буфер.

На практике вам не нужен полный просмотр времени. В большинстве случаев достаточно одного токена. Вы должны структурировать код в качестве дерева решений, где в случае необходимости необходимо использовать только токены для устранения двусмысленности. (Часто бывает полезно указать специальный токен типа «неизвестный», который можно присвоить буферизованному списку токенов, чтобы указать, что lookahead еще не достиг этой точки. В качестве альтернативы вы всегда можете поддерживать токены k, для которые могут быть проще.)

В качестве альтернативы вы можете использовать резервную структуру, в которой вы просто попробуете одну альтернативу, и если это не сработает, вместо сообщения о синтаксической ошибке восстановите состояние анализатора и лексера к следующей альтернативе. В этой модели лексер принимает в качестве явного аргумента текущую позицию входного буфера, а входной буфер должен быть перемотируемым. Однако вы можете использовать буфер lookahead для эффективной memoize функции lexer, которая позволяет избежать перемотки и повторного сканирования. (Сканирование, как правило, достаточно быстро, что иногда заново сканируется не имеет значения, так что вы можете отложить усложняя код, пока ваш профилирование не указывает на то, что было бы полезно.)

Два примечания:

1) I» м скептически относится к правилу:

functionCall : ID'(' (expression (',' expression)*)* ')' 
      ; 

Это позволило бы, например:

function(a[3], b[2] c[x] d[y], e.foo) 

который не смотрит прямо на меня. Обычно вы отмечаете содержимое () как по выбору вместо повторяется, напр. используя необязательный маркер ? вместо второго Клини звезды *:

functionCall : ID'(' (expression (',' expression)*)? ')' 
      ; 

2) По-моему, вы действительно должны рассмотреть возможность использования снизу вверх разбора для языка выражений, либо сгенерированный LR(1) парсер или ручной встроенный Пратт анализатор , LL(1) редко бывает адекватным. Конечно, если вы используете генератор парсера, вы можете использовать инструменты, такие как ANTLR, которые эффективно реализуют LL(∞); который позаботится о вас.