Python rply обратный парсер - PullRequest
Новая
       21

Python rply обратный парсер

2 голосов
/ 05 апреля 2019

Я использую rply и Python3.6 для создания лексера и парсера для небольшого приватного проекта.

Но я заметил, что парсер переворачивает порядок лексерстрима.

Это файл, который я анализирую: 

let test:string = "test";
print(test);

Вывод Lexer: 

Token('LET', 'let')
Token('NAME', 'test')
Token('COLON', ':')
Token('NAME', 'string')
Token('EQUALS', '=')
Token('STRING', '"test"')
Token('SEMI_COLON', ';')
Token('PRINT', 'print')
Token('OPEN_PARENS', '(')
Token('STRING', '"test"')
Token('CLOSE_PARENS', ')')
Token('SEMI_COLON', ';')

Как вы можете видеть, это в порядке сценария.

Я использую парсер для создания переменной с именем test, типом string и значением test.Затем я хочу напечатать переменную.

Она создает переменную, но когда я хочу распечатать ее, ничего нет.

Но когда я переворачиваю скрипт, как это 

print(test);
let test:string = "test";

он может правильно печатать значение.

Два «правила» синтаксического анализатора выглядят так: Print: 

@self.pg.production('expression : PRINT OPEN_PARENS expression CLOSE_PARENS SEMI_COLON expression')
def print_s(p):
    ...

Создать переменную: 

@self.pg.production('expression : LET expression COLON expression EQUALS expression SEMI_COLON expression')
def create_var(p):
    ...

Итак, мой вопрос: как я могу изменить порядок анализа содержимого?

Редактировать: Я искал похожие вопросы или проблемы, а также в документации, но ничего не нашел.

1 Ответ

2 голосов
/ 06 апреля 2019

Вот несколько более простой пример;надеюсь, вы можете увидеть шаблон.

Ключевым моментом является то, что действия сокращения (то есть функции синтаксического анализатора) выполняются, когда совпадение производства полностью проанализировано.Это означает, что если производство содержит нетерминалы, действия для этих нетерминалов выполняются перед действием для всего производства.

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

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

  1. Правая рекурсия: 

    list : thing list

  2. Левая рекурсия: 

    list : list thing

В обоих случаях действие печатает thing, то есть p[0] в праворекурсивном случае, иp[1] в лево-рекурсивном.

Право-рекурсивное производство приведет к печати thing s в обратном порядке, потому что печать thing происходит только после внутреннего *Разбирается 1032 * (и его компоненты печатаются).

Но леворекурсивное производство напечатает thing s в порядке слева направо по той же причине.Разница tgat в лево-рекурсивном случае, внутренний (рекурсивный) list содержит начальные thing с, а в праворекурсивном случае list содержит конечные thing с.

Если бы вы только создавали список Python из thing s, это, вероятно, не имело бы большого значения, поскольку порядок выполнения не был бы важен.Это видно только в этом примере, потому что у действия есть побочный эффект (печать значения), что делает порядок выполнения видимым.

Существуют другие методы для упорядочения действий, в редких случаяхгде это действительно необходимо.Но лучшая практика - всегда использовать левую рекурсию, когда это синтаксически практично.Леворекурсивные парсеры более эффективны, потому что парсер не должен накапливать стек незавершенных производств.И левая рекурсия часто лучше для ваших действий.

Здесь, например, леворекурсивное действие может добавить новое значение (p[0].append(p[1]); return p[0]), тогда как праворекурсивное действие должно создать новый список (return [p[0] + p[1]).Поскольку повторное добавление выполняется в среднем по линейному времени, а повторное объединение является квадратичным, леворекурсивный синтаксический анализатор более масштабируем для больших списков.

...