Я где-то задавал вопрос о различии между парсерами LL (0) и LR (0). Есть ли такие вещи, как LL (0) парсеров? Если да, то как они анализируются, не глядя на какой-либо токен?
Есть ли такие вещи, как LL (0) парсеров?
Ответ 1
LL (0) парсеры действительно смотрят на токены, но они не решают, какие производства применять на них. Они просто определяют, принадлежит ли эта последовательность языку или нет. Это означает, что каждый нетерминальный символ должен иметь одну правую часть и что рекурсия не может быть.
G == ID name lastname
name == STRING
lastname == STRING
# lexer rules
# -----------
ID == [0-9]+
STRING == <unicode>+
Обратите внимание, что, как упоминалось в @280Z28, для обработки частей переменной длины (ID и STRING) необходим отдельный лексер, или грамматика не будет LL(0).
Последовательность производств, применяемая для синтаксического анализа ввода с помощью этой грамматики, требует нулевого представления.
Для детерминизма требуется просмотр, когда было проанализировано более одного производства, которое может быть применено после того, как часть данной входной последовательности была проанализирована.
В теории грамматика генерирует язык, и в этом случае двусмысленность (имеющая более чем один способ получения данной фразы) прекрасна. При синтаксическом анализе использование метода "один-единственный-один" на пути семантики (значения), и это то, что мы хотим.
При анализе языков программирования взгляд на информацию - это информация, необходимая для того, чтобы знать, какую грамматическую работу использовать далее.
В языках LL (0) нет выбора, поэтому входная последовательность либо принимается, либо анализируется, либо отклоняется.
Ответ 2
k в LR (k) относится к числу токенов. Вы всегда используете хотя бы один токен, чтобы определить действие для выполнения. На странице Wikipedia page есть дополнительная информация об этом.
Интуитивно, дополнительные символы с надписью позволяют вам делать варианты выбора с большей информацией, поэтому они позволяют выражать большие классы грамматик без конфликтов.
Ответ 3
Когда я брал компиляторы, мы никогда не говорили о них, хотя мы говорили о LL (1). Там нет упоминания о них Wikipedia.
Парсер LL (0) будет означать, что синтаксический анализатор может принять решение, не зная следующего токена в потоке. Я бы ожидал, что если языки с этим свойством существуют, они редко встречаются редко.