Как грамматика Python используется внутри?

Грамматика используется для описания всех возможных строк в языке. Это также полезно для указания того, как синтаксический анализатор должен анализировать язык.

В этой грамматике создается впечатление, что они используют собственную версию EBNF, где нетерминал — это любое слово в нижнем регистре, а терминал — все в верхнем регистре или в кавычках. Например, NEWLINE — это терминал, arith_expr — это нетерминал, а if — тоже терминал. Любой нетерминал может быть заменен чем угодно справа от двоеточия соответствующего производственного правила. Например, если вы посмотрите на первое правило:

single_input: NEWLINE | простой_stmt | соединение_stmt NEWLINE

Мы можем заменить single_input на один из NEWLINE, simple_stmt или составной_stmt, за которым следует NEWLINE. Предположим, мы заменили его на «compound_stmt NEWLINE», тогда мы будем искать правило производства для compound_stmt:

соединение_stmt: if_stmt | пока_stmt | for_stmt | попытка_stmt | с_stmt | функция | определение класса | украшен

и выберите, какой из них мы хотим использовать, и замените его на «compound_stmt» (сохраняя NEWLINE на своем месте)

Предположим, мы хотим сгенерировать валидную программу на Python:

if 5 < 2 + 3 or not 1 == 5:
    raise

Мы могли бы использовать следующий вывод:

1. single_input
2. соединение_stmt NEWLINE
3. if_stmt NEWLINE
4. 'если' тест ':' комплект NEWLINE
5. 'if' or_test ':' NEWLINE INDENT stmt stmt DEDENT NEWLINE
6. 'if' and_test 'или' and_test ':' NEWLINE INDENT simple_stmt DEDENT NEWLINE
7. 'if' not_test 'или' not_test ':' NEWLINE INDENT small_stmt DEDENT NEWLINE
8. 'if' сравнение 'или' 'не' not_test ':' NEWLINE INDENT flow_stmt DEDENT NEWLINE
9. 'if' expr comp_op expr 'или' 'не' сравнение ':' NEWLINE INDENT raise_stmt DEDENT NEWLINE
10. 'if' arith_expr '‹' arith_expr 'или' 'не' arith_expr comp_op arith_expr ':' NEWLINE INDENT 'raise' DEDENT NEWLINE
11. 'if' term '‹' term '+' term 'or' 'not' arith_expr == arith_expr ':' NEWLINE INDENT 'raise' DEDENT NEWLINE
12. 'if' ЧИСЛО '‹' ЧИСЛО '+' ЧИСЛО 'или' 'не' ЧИСЛО == ЧИСЛО ':' ОТСТУП ОТ НОВОЙ СТРОКИ 'поднять' ОТСТУП ОТ НОВОЙ СТРОКИ

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

Учитывая строку в языке, как мы находим ее происхождение? Это работа парсера. Синтаксический анализатор реконструирует производственную последовательность, чтобы сначала проверить, действительно ли это допустимая строка, и, кроме того, как ее можно получить из грамматики. Стоит отметить, что многие грамматики могут описывать один язык. Однако для данной строки вывод, конечно, будет разным для каждой грамматики. Так что технически мы пишем парсер для грамматики, а не для языка. Некоторые грамматики легче анализировать, некоторые грамматики легче читать/понимать. Этот относится к первому.

Также это не указывает весь язык, а только то, как он выглядит. Грамматика ничего не говорит о семантике.

Если вас интересуют дополнительные сведения о синтаксическом анализе и грамматике, я рекомендую Grune, Jacobs — Методы синтаксического анализа. Это бесплатно и хорошо для самостоятельного изучения.

Грамматика Python, как и большинство других, представлена ​​в BNF или Backus–Naur Form. . Попробуйте прочитать, как это читать, но основная структура такова:

<something> ::= (<something defined elsewhere> | [some fixed things]) [...]

Это читается как <something> определяется как something else или любая из фиксированных вещей, повторяющихся множество раз.

BNF основан на почти 2000-летнем формате описания разрешенной структуры языка, он невероятно лаконичен и описывает все допустимые структуры в данном языке, не обязательно все те, которые имеют смысл.

Пример

Базовую арифметику можно описать так:

<simple arithmetic expression> ::= <numeric expr>[ ]...(<operator>[ ]...<numeric expr>|<simple arithmetic expression>)
<numeric expr> ::= [<sign>]<digit>[...][.<digit>[...]]
<sign> ::= +|-
<operator> ::= [+-*/]
<digit> ::= [0123456789]

В котором говорится, что простая арифметическая операция представляет собой число, необязательно со знаком, состоящее из одной или нескольких цифр, возможно, с десятичной точкой и одной или несколькими последующими цифрами, за которыми могут следовать пробелы, за которыми следует ровно одна из +-*/, за которыми может следовать пробелы, за которыми следует либо число, либо другая простая арифметическая операция, т. е. число, за которым следует число, и т. д.

Здесь описываются почти все основные арифметические операции, и его можно расширить, включив в него функции и т. д. Обратите внимание, что разрешены недопустимые операции, которые являются допустимым синтаксисом, например: 22.34 / -0.0 является синтаксически допустимым, несмотря на то, что результат недействителен.

Иногда это может дать вам понять, что возможны операции, о которых вы, возможно, не думали, например: 56+-50 является допустимой операцией, как и 2*-10, но 2*/3 нет.

Обратите внимание, что SGML и XML/Схема связаны между собой, но это разные методологии описания структуры любого язык. YAML — это еще один метод описания разрешенных структур в компьютерных языках.

Отказ от ответственности: мой BNF немного заржавел, поэтому, если я допустил какие-либо серьезные ошибки в приведенном выше, приношу извинения и, пожалуйста, поправьте меня.

По сути, это спецификация EBNF (расширенная форма Бэкуса-Наура).

Когда вы пишете программу на языке, самое первое, что должен сделать ваш интерпретатор/компилятор, чтобы перейти от последовательности символов к реальному действию, — это преобразовать эту последовательность символов в более сложную структуру. Для этого сначала он разбивает вашу программу на последовательность токенов, выражающих то, что представляет каждое «слово». Например, конструкция

if foo == 3: print 'hello'

будет преобразован в

1,0-1,2:    NAME    'if'
1,3-1,6:    NAME    'foo'
1,7-1,9:    OP  '=='
1,10-1,11:  NUMBER  '3'
1,11-1,12:  OP  ':'
1,13-1,18:  NAME    'print'
1,19-1,26:  STRING  "'hello'"
2,0-2,0:    ENDMARKER   ''

Но обратите внимание, что даже что-то вроде «если бы если бы если» правильно превращается в токены.

1,0-1,2:    NAME    'if'
1,3-1,5:    NAME    'if'
1,6-1,8:    NAME    'if'
1,9-1,11:   NAME    'if'
2,0-2,0:    ENDMARKER   ''

За токенизацией следует анализ структуры более высокого уровня, которая анализирует, действительно ли токены имеют смысл вместе взятые, чего нет в последнем примере, но делает первый. Для этого синтаксический анализатор должен распознать фактическое значение токенов (например, if — это ключевое слово, а foo — переменная), затем построить дерево из токенов, организовав их в иерархию, и посмотреть, действительно ли эта иерархия создает смысл. Вот тут-то и появляется грамматика, которую вы видите. Эта грамматика находится в BNF, которая представляет собой нотацию для выражения конструкций, которые может распознать язык. Эта грамматика переваривается программой (например, bison), которая обладает волшебным свойством брать эту грамматику и генерировать фактический код C, который делает за вас тяжелую работу, обычно распознавая токены, организуя их, возвращая вам дерево синтаксического анализа, или сказать вам, где есть ошибка.

Краткая версия: разработка языка заключается в определении токенов и о том, как эти токены объединяются, чтобы дать что-то значимое. Это делается с помощью грамматики, которую вы используете для создания фактического кода «парсера» с помощью автоматизированных инструментов.