Является ли грамматика Python LL (1)? - PullRequest
Новая
       29

Является ли грамматика Python LL (1)?

0 голосов
/ 03 декабря 2018

Возможный дубликат для этого вопроса однако для меня это недостаточно конкретно.

Грамматика питона заявлена ​​как LL (1) , но язаметил некоторые выражения в грамматике Python , которые действительно меня смущают, например, аргументы в следующем вызове функции: 

foo(a)
foo(a=a)

соответствует следующей грамматике: 

argument: ( test [comp_for] |
            test '=' test |
            '**' test |
            '*' test )

test появляется дважды в первой позиции грамматики.Это означает, что, только взглянув на test, Python не может определить, является ли он test [comp_for] или test '=' test.

Дополнительные примеры: 

comp_op: '<'|'>'|'=='|'>='|'<='|'<>'|'!='|'in'|'not' 'in'|'is'|'is' 'not'

Примечание 'is' и 'is' 'not'

subscript: test | [test] ':' [test] [sliceop]

test также появляется дважды.

Это мойпонимание LL (1) неправильно?Делает ли Python обходной путь для грамматики во время лексирования или анализа, чтобы сделать ее LL (1) обрабатываемой?Спасибо всем заранее.

Ответы [ 2 ]

0 голосов
/ 03 декабря 2018

Грамматика , представленная в документации Python (и используемая для генерации синтаксического анализатора Python), записана в форме расширенного BNF, который включает в себя такие «операторы», как необязательность ([a]) и закрытие Kleene ((a b c)*).LL (1), однако, является категорией, которая применяется только к простым контекстно-свободным грамматикам, которые не имеют таких операторов.Поэтому вопрос о том, является ли эта конкретная грамматика LL (1) или нет, является ошибкой категории.

Чтобы сделать вопрос осмысленным, грамматику необходимо преобразовать в простую контекстную грамматику без контекста.Это, конечно, возможно, но нет канонического преобразования, и документация Python не объясняет точное используемое преобразование.Некоторые преобразования могут создавать грамматики LL (1), а другие - нет.(Действительно, наивный перевод звезды Клини может легко привести к неоднозначности, которая по определению не является LL (k) для любого k.)

На практике аппарат синтаксического анализа Python преобразует грамматику в исполняемый синтаксический анализатор,не в контекстно-свободной грамматике.Для прагматических целей Python достаточно создать прогнозирующий синтаксический анализатор с прогнозом всего на один токен.Поскольку прогнозирующий синтаксический анализатор может использовать управляющие структуры, такие как условные операторы и циклы, полное преобразование в контекстно-свободную грамматику не требуется.Таким образом, можно использовать производства EBNF - как с документированной грамматикой - которые не являются полностью левосторонними, и даже производства EBNF, преобразование которых в LL (1) нетривиально: 

simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE

В вышеприведенном производстве повторение (';' small_stmt)* может сопровождаться ';', что означает, что простой цикл while не будет правильно представлять производство.Я не знаю, как эта продукция обрабатывается генератором синтаксического анализатора Python, но можно преобразовать его в CFG с помощью левого факторинга после расширения повторения: 

simple_stmt: small_stmt rest_A
rest_A     : ';' ret_B
           | NEWLINE
rest_B     : small_stmt rest_A
           | NEWLINE

Аналогично, весь EBNF может бытьпревращается в LL (1) грамматику.Это не сделано, потому что упражнение бесполезно ни для разбора, ни для объяснения синтаксиса.Это было бы трудно читать, и EBNF может быть непосредственно преобразован в парсер.

Это немного не зависит от вопроса, является ли Python LL (1), потому что язык - LL (1), точно еслидля языка существует грамматика LL (1).Всегда будет бесконечно много возможных грамматик для языка, включая грамматики, которые не являются LL (k) для любых k, и даже грамматики, которые не являются контекстно-свободными, но это не имеет отношения к вопросу о том, является ли язык 1021 * - это LL (1): язык - LL (1), если существует хотя бы одна грамматика LL (1).(Я знаю, что это не оригинальный вопрос, поэтому я не буду заниматься этим дальше.)

0 голосов
/ 03 декабря 2018

Вы правы, что конструкции типа 'is' | 'is' 'not' не являются LL (1).Их можно легко преобразовать в LL (1), изменив его на 'is' notOpt, где notOpt: 'not' | ϵ или, если вы разрешите синтаксис EBNF, просто 'is' 'not'? (или 'is' ['not'] в зависимости от разновидности EBNF).

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

...