Как парсер LR(1) обрабатывает пустые правила?

Я работал с несколькими парсерами (Yacc, Bison и Menhir). Если я правильно помню, все они допускают, чтобы правило было пустым. Вот пример того, что я имею в виду под Менгиром, это то, что я использовал чаще всего.

some_list:
 | {[]}
 | some_non_empty_list { $1 }

some_non_empty_list:
 | SEMICOLON some_list { $2 }
 | element { [$1] }
 | element some_non_empty_list { $1 :: $2 }

Важная часть заключается в том, что some_list может свести на нет.

Мое нынешнее понимание алгоритма построения таблицы синтаксического анализа (построение NFA, построение DFA из NFA, минимизация) заставляет меня думать, что это приведет к конфликтам сдвига/уменьшения повсюду. Но это явно не так, потому что тогда мой код работал.

Итак, как построить таблицу синтаксического анализа, которая может принимать эти пустые правила?


parsing finite-automata menhir
person Olivier Melançon    schedule 01.04.2017    source источник
comment
Как вы думаете, почему с пустым правилом работать сложнее, чем с правилом с одним правым токеном?   -  person Ira Baxter    schedule 02.04.2017
comment
Моя интуиция заключалась в том, что пустое правило означает, что его можно сократить в любое время, но ваш вопрос как бы заставляет меня думать, что это понимание неверно. Я еще не мог понять, как мы строим таблицы синтаксического анализа. Я думал, что это похоже на создание лексической таблицы, за исключением того, что вы не допускаете конфликтов.   -  person Olivier Melançon    schedule 04.04.2017
comment
Упрощая, правило грамматики L = R1 R2 R3 ; означает уменьшить до L, если вы видите R1 R2 R3. На самом деле, это неправильно. Если мы имеем X= A L B ; тогда наше правило L означает сокращение до L, если ваш левый контекст — это A, вы видели R1 R2 R3, а следующий токен — первый (B). Работает так же, если L = R1 R2 ; и L = R1 ;. И предельный случай: L = ; (пустое правило). Вы не можете свести к L, если вы не видели его левый контекст, его содержание и начало того, что следует за ним. Таким образом, вы не можете свести к пустому правилу в любое время. ...   -  person Ira Baxter    schedule 04.04.2017
comment
... Что вам нужно сделать, так это узнать, как работают синтаксические анализаторы LR, научившись отслеживать наборы элементов при построении состояний синтаксического анализа. Сделайте это на бумаге, один раз, (мучительно да, стоит того да) для небольшой грамматики, и парсеры LR все станут понятны. Вы можете найти описание этого процесса в любой книге по разбору LR, включая классические компиляторы Aho et al.   -  person Ira Baxter    schedule 04.04.2017

Ответы (1)


arrow_upward
1
arrow_downward

Как вы думаете, почему с пустым правилом работать сложнее, чем с правилом с одним правым токеном?

Упрощая, правило грамматики L = R1 R2 R3 ; означает «уменьшить до L, если вы видите R1 R2 R3». Не упрощая, если мы имеем X= A L B ; тогда наше правило L означает «сократить до L, если ваш левый контекст — это A, вы видели R1 R2 R3, а следующий токен — первый (B).

Эта идея остается той же, если L = R1 R2; и L = R1 ;.

И даже для предельного случая (пустое правило): L = ;

Вы не можете свести к L, если вы не видели его левый контекст, его содержание и начало того, что следует за ним. Таким образом, вы не можете свести к пустому правилу «в любое время».

Что вам нужно сделать, так это узнать, как работают синтаксические анализаторы LR, научившись отслеживать наборы элементов при построении состояний синтаксического анализа. Сделайте это на бумаге, один раз, (мучительно да, стоит того да) для небольшой грамматики, и парсеры LR все станут понятны. Вы можете найти описание этого процесса в любой книге по разбору LR, включая классические компиляторы Aho et al.

person Ira Baxter    schedule 10.10.2018