Повторения Анализ грамматики S -> (E ';') + - PullRequest
Новая
       75

Повторения Анализ грамматики S -> (E ';') +

1 голос
/ 09 мая 2020

Я знаю, как разбирать грамматики следующим образом: 

E -> E '*' E
E -> E '+' E
E -> N
N -> '0'
N -> '1'

Но что, если у меня есть следующий пример грамматики (с «повторением регулярного выражения»): 

E -> 'e'
S -> ( E ';' )+ // '+' used like in regexes

Как можно я разбираю такие грамматики с помощью LR (k) (или другого алгоритма синтаксического анализа) и строю дерево?

1 Ответ

1 голос
/ 09 мая 2020

Это либо 

S → E ';'
S → S E ';'

, или 

S → E ';'
S → E ';' S

В вашем первом фрагменте, в котором вы говорите, что вы «умеете разбирать», ваша грамматика неоднозначна. Я предполагаю, что вы анализируете его с помощью каких-то внешних объявлений приоритета / ассоциативности, поскольку синтаксический анализ не может быть осмысленно применен к тексту для целей, отличных от простого распознавания, без указания того, как должно быть построено дерево синтаксического анализа. Грамматики, которые я здесь привожу, не двусмысленны и, таким образом, воплощают ассоциативность списков. Во многих случаях ассоциативность списка не имеет значения, поскольку желаемый результат - это просто список; в таком случае не имеет значения (грамматически), какую из вышеперечисленных альтернатив вы выберете.

Обычно при использовании генератора парсера LR мы выбираем левоассоциативный, который является первым из приведенных выше . Это потому, что правоассоциативность требует сохранения отдельных элементов в стеке синтаксического анализатора до тех пор, пока список не будет окончательно построен, от начала до конца, когда вы дойдете до конца. Таким образом, анализ длинного списка может занять много стека парсера; если ваш генератор парсера ограничивает размер стека, это в конечном итоге станет проблемой.

Построение списка от начала к началу может также сбить с толку новичков. Распространенная путаница (судя по вопросам по SO) происходит из следующего кода "отладки" (в синтаксисе yacc / bison): (Для простоты я реализую (E ';')* вместо (E ';')+; в большинстве случаев это то, что вам нужно в любом случае.) 

list: %empty
    | element ';' list { printf("Adding %s\n", $1); }

Это приведет к тому, что элементы в списке будут распечатаны справа налево, что нормально, если это то, что вы ожидаете от кода. Но часто это приводит к путанице, что несколько контрпродуктивно для отладки кода. (Это лишь одна из причин, по которой я всегда рекомендую использовать инструменты отладки, встроенные в ваш генератор парсера, и всегда выбирать генератор парсера, который имеет встроенные инструменты отладки, а не пытаться создать следы парсера волей-неволей с набором ad ho c print операторов.)

Если синтаксический анализатор является, например, частью непосредственного калькулятора, обратная оценка явно будет огромной ошибкой. Вы хотите оценивать, а затем отбрасывать выражения по одному, слева направо и ассоциативность слева будет обязательной.

Но это не всегда так. Предположим, мы выполняем синтаксический анализ с целью создания AST (или другого промежуточного продукта, который приведет к генерации кода). И предположим, что элементы здесь являются операторами, а список представляет собой блок (за вычетом разделителей блоков, которые будут прикреплены к некоторому внешнему продукту). В языках, в которых объявления в блоке являются локальными по отношению к блоку и охватываются от объявления до конца блока, семантика программы настоятельно предполагает правильную ассоциативность. Рассмотрим следующий немного глупый пример: 

1    function example(i: integer)
2       var tmp: integer = i;
3       var i: integer = tmp - 1;
4       return tmp * i;
5    end

Здесь область действия tmp простирается от оператора 2 до конца оператора 4. Область действия i в списке параметров расширяется от оператора 1 до оператора 5, но в операторе 3 он затеняется объявлением другой переменной с тем же именем, чья область действия простирается от оператора 3 до конца оператора 4.

Для осмысленного синтаксического анализа этого языка мы я захочу создавать новую подобласть каждый раз, когда мы видим объявление, и присоединять эту подобласть к той части программы, которая запускается сразу после объявления. Это может предложить грамматику примерно такого вида: 

block: %empty
     | declaration ';' block { $3.set_scope(new Scope($1));
                               $3.prepend($1.initialiser()); }
     | statement ';' block   { $3.prepend($1); }

Просто чтобы прояснить: есть хорошо известные идиомы для преобразования 

S → A B*

и 

S → B* A

в контекстно-свободные грамматики. Первый - 

S: A
 | S B

Второй - 

S: A
 | B S

Если A равен B (другими словами, если вы хотите S → B+, что представляет то же самое текст как S → B B* или S → B* B, вы должны использовать S: B | S B или S: B | B S. Я не делал этого выше, потому что это включает в себя повторение B и любого действия, соответствующего ему, что раздражает, если B не является отдельным символом. Нет ничего плохого в повторении B (или создании промежуточного нетерминала для его представления, если это действительно сложно или имеет сложное действие), но было проще избежать проблемы.

...