Разработка компиляторов и интерпретаторов
Способы описания синтаксиса
Для формального описания структуры входных данных, синтаксиса языков программирования используют несколько способов. Наиболее подходящими для компьютерной обработки являются синтаксические правила в форме Бэкуса-Наура (БНФ), которая применялась при описании языка Алгол. Аналогично RE такое формальное описание может использоваться для описания формата входных данных в спецификации, проверки корректности и генерации случайных тестовых данных.
В отличии от RE синтаксические правила позволяют описывать более сложные зависимости, например, соответствие открывающихся и закрывающихся скобок:
В первоначальной версии БНФ нетерминальные символы (те, для которых есть определение) записывались в угловых скобках, а терминальные записывались без кавычек и только метасимволы необходимо было писать в кавычках.
Затем была предложена расширенная БНФ (есть стандарт ISO/IEC 14997:1996), в которой определение нетерминального символа необходимо было заканчивать символом ;, все терминальные символы записывать в кавычках или апострофах, а последовательность символов записывать через запятую. Были добавлены метасимволы <> для повторения конструкции ноль или более раз, [] для опциональной части конструкции, () для группировки, * для повторения конструкции заданное количество раз (5*" " – 5 пробелов), - для исключения варианта, а вместо ::= предлагалось писать просто =:
digit = ?цифра от 0 до 9? ; natural number = digit - "0", < digit >; integer = "0" | [ "-" ], natural number ;
РБНФ позволяет описать синтаксис языка более компактно по сравнению с БНФ. Если грамматика языка является LL(k), то можно сгенерировать программу для синтаксического разбора методом рекурсивного спуска с помощью COCO/R, JavaCC или ANTLR.
БНФ обычно применяется для описания LR(k)-грамматик, в которых разбор выполняется снизу вверх. Это позволяет лучше выявлять и обрабатывать ошибки синтаксиса, но правила могут иметь только простую структуру, так как их применение возможно только после полного распознавания конструкции. Поэтому вместо циклических определений нужно использовать рекурсивные:
БНФ: ::= () | () ::= | , РБНФ: function call = name, "(", [ arg, < ",", arg >], ")" ;
Способ перевода из РБНФ в БНФ показан в таблице.
Очень наглядны описания синтаксиса в графической форме, использованные Виртом для языков Паскаль и Модула, но они не слишком удобны для ввода и обработки компьютером:
Что такое форма Backus-Naur ?
Синтаксис командной строки QlikView и синтаксис скриптов описываются в нотации, называемой формой Backus-Naur , известной также как код BNF .
В следующей таблице представлен список символов, используемых в коде BNF , с описанием их интерпретации:
| Символ | Описание |
|---|---|
| | | Логическая операция OR : символ можно использовать с любой стороны. |
| ( ) | Скобки очередности выполнения: используются для структурирования синтаксиса BNF . |
| [ ] | Квадратные скобки: заключенные в них элементы являются необязательными. |
| Фигурные скобки: заключенные в них элементы могут повторяться ноль и более раз. | |
| Символ | Нетерминальная синтаксическая категория: может быть разделена на другие символы. Например на составляющие вышеуказанного, другие нетерминальные символы, текстовые строки и т. д. |
| ::= | Отметка начала блока, определяющего символ. |
| LOAD | Терминальный символ, состоящий из текстовой строки. Записывается как есть в скрипт. |
Все терминальные символы напечатаны полужирным шрифтом. Например, «(» следует интерпретировать как скобки, определяющие порядок выполнения, а « ( » следует интерпретировать как символ скрипта.
Описание оператора alias:
alias fieldname as aliasname
Это следует интерпретировать как текстовую строку «alias», за которой следует произвольное имя поля, а потом текстовая строка «as» и произвольное имя псевдонима. Можно задать любое число дополнительных комбинаций « fieldname as alias », используя запятую в качестве разделителя.
Например, верными являются следующие операторы:
alias a as first;
alias a as first, b as second;
alias a as first, b as second, c as third;
Следующие операторы являются неверными:
alias a as first b as second;
Бнф что это программирование
Формы Бэкуса-Наура (БНФ).
Как программируют трансляторы? Этот вопрос давно интересовал меня. Году в 1998 я, программируя функции для обработки строк, сам, «своим путем», продвинулся «на некоторую глубину» в этом направлении. Но потом пришел к выводу, что все-таки лучше сперва ознакомиться с тем, что наработано человечеством в этой области компьютерной науки. Далеко не сразу мне попалась литература, которую можно было нормально прочитать. То же относится и к статьям в Интернете. Причем, я бы не сказал, что мне попались отличные источники. Которые прочитал – и все понял, ничего больше не надо. Нет, то здесь, то там были рассеяны отдельные крупицы знаний, которые еще надо было перерабатывать и осмысливать своими мозгами. Однажды я скачал (и распечатал) даже исходник транслятора Бэйсика. Но заняться им сразу руки не дошли, а потом я с огорчением обнаружил, что потерял распечатку.
Кстати, пока под транслятором я подразумеваю и компиляторы, и интерпретаторы.
Оказалось, что в основе программирования трансляторов лежит целая математическая теория. Раздел не то дискретной математики, не то теории множеств. И главное здесь – это грамматики и формы Бэкуса-Наура.
В математические определения, связанные с грамматиками, я здесь вдаваться не буду. Если вам интересно – прочитайте соответствующую книгу или статью. Скажу только, что прежде всего есть так называемый алфавит – некое множество символов. Из этих символов составляются некоторые сочетания (можно назвать их словами). А уже эти сочетания составляют текст (если это грамматика обычного человеческого языка) или программу (если это грамматика языка программирования). Текст может быть правильным (то-есть составленным по правилам этой грамматики) или неправильным. И основная задача теории – определить, правильный или неправильный этот текст. Правила «кодируются» с помощью своеобразных конструкций – форм Бэкуса-Наура.
Попробую дать определение этих форм. Каждая форма – это некоторая строчка.
Есть знак := . Он отделяет левую часть строки от правой.
Есть так называемые «терминалы» — это, грубо говоря, то, из чего состоит язык. Допустим, человеческий язык состоит из предложений, предложения – из слов, слова бывают подлежащими и сказуемыми. Слова же в свою очередь состоят из букв. Предложения, слова, подлежащие и сказуемые, буквы – это все терминалы. Впрочем, буквы называют еще терминальными символами.
Если же мы имеем строку арифметического выражения, то она состоит из множителей (или делимых-делителей), а также из слагаемых, а они в свою очередь состоят из чисел. Причем слагаемое само может состоять из слагаемых. Например :
Слагаемое 1+2 само состоит из двух слагаемых – 1 и 2. Это – важный пункт.
Терминалы часто как-то «обзываются» — например «множ» или “ factor ” (что вообще говоря должно обозначать одно и тоже – множитель.
И, наконец, есть «нетерминалы» — < и >. Они как скобки обрамляют некоторые терминалы.
Есть еще знак | — он разделяет несколько альтернативных терминалов.
Наверное, пока непонятно, но все нужно смотреть и постигать на примерах.
Это все самый «простейший» вариант форм Бэкуса-Наура. Есть и усложнения. Допустим, некоторые конструкции (в правой части строки) можно взять в квадратные скобки ([ … ]). Это означает, что конструкция может отсутствовать (то-есть или присутствует один раз, или отсутствует). А если без таких скобок – значит присутствует строго один раз.
Есть и фигурные скобки (< … >). «Обрамленная» ими конструкция повторяется некоторое (возможно нулевое) количество раз.
Встречал я и такие скобки: . Это означает повторение 1 или большее количество раз (то-есть ненулевое количество).
Есть и другие разночтения в определениях форм. Бывает, например, что опускают нетерминалы < и >.
Кстати, насчет скобок. Я бы ввел еще один вид скобок, означающий повторение определенное количество раз. Обозначение может быть таким:
– повторение 5 раз. В некоторых случаях это может оказаться полезным.
Теперь приступим к примерам.
1) Дадим определение идентификатору с помощью БНФ (то-есть форм Бэкуса-Наура):
Основная идея такого формализма понятна, я надеюсь. Идентификатор начинается обязательно с буквы, а дальше идет некоторое количество букв или цифр. В этом смысл вышеприведенных 3-х строк.
A B A1 B2C3 DA123
Отметим тут же, что всегда есть «самый главный» терминал (и, соответственно, главная строка, в левой части которой он находится), соответствующий тому объекту, который мы исследуем. В данном случае исследуем мы идентификатор, а самый главный терминал – это «Идент».
2) Грамматика целых чисел без знака:
Обратим внимание, что терминал «число» встречается в первой строке 2 раза. Это важный момент. В дальнейшем он приведет к появлению рекурсии (когда мы будем программировать).
3) Формула с плюсами и минусами без скобок.
Что такое число – это можно было бы продолжить, приписывая строки примера 2.
Можно было бы записать и такую форму для этого случая:
А если и числа, и переменные, то:
4) Формула с плюсами и минусами со скобками.
Обратим внимание, что во второй строке появились скобки. « Op » – это некоторый промежуточный терминал, введенный для удобства.
5) Формула с плюсами и минусами, а также с умножением и делением без скобок. Входят в формулу не только числа, но и переменные.
То-есть, самые крупные блоки, которые мы выделяем из строки с формулой – это слагаемые. Заметим, что этим определяется самый низший приоритет операций сложения-вычитания. Обратим внимание еще на то, что левое слагаемое уже не состоит из вложенных слагаемых, в отличие от правого.
6) Формула с плюсами и минусами, с умножением и делением без скобок, а также с унарным плюсом-минусом (причем унарный знак может присутствовать перед числом или переменной лишь в единственном числе).
7) Формула с плюсами и минусами, умножением и делением и со скобками.
8) Добавляем функции (встроенные) одного переменного (пусть это будут для примера sin и cos ).
Есть еще альтернативный подход к описанию правил грамматики. Это диаграммы Вирта. Вирт, кстати, это создатель языка Паскаль.
Описания того, что есть что в диаграммах Вирта, я нашел в Интернете. Но скажу честно, понимается это с трудом. Опишу вкратце на словах. Нечто, обведенное кружком – это терминальный символ. Есть еще нечто, заключенное в прямоугольник – это «постоянная группа терминальных символов, определяющая название лексемы, ключевое слово и др.». То-есть в кружок и прямоугольник заключаются терминалы (то, что мы имели ввиду под терминалами в формах Бэкуса-Наура).
Есть еще «нетерминальный символ, определяющий название правила». Это, по-видимому, то, что в формах Бэкуса-Наура мы ставили в левой части строки, слева от знака «:=».
И есть еще соединительные линии. Они «обеспечивают связь между терминальными и нетерминальными символами». Эти линии расходятся, потом сходятся снова, проходя через кружки и прямоугольники. Иногда образуют циклические петли, касающиеся основной горизонтальной линии.
Диаграмма состоит из нескольких «рисунков», также, как БНФ – из нескольких строк. На одном рисунке всегда есть основная горизонтальная линия, в начале которой написано название правила. Это аналог одной строки из формы Бэкуса-Наура. Если далее линия раздваивается, то это аналог выбора одной из двух альтернатив в БНФ (напомню, что эти альтернативы разделяются знаком | ). Если же есть зацикленная линия (петля), касающаяся основной линии, то это аналог рекурсивной части строки Бэкуса-Наура, то-есть часть этой строки (справа) совпадает с левой частью строки. Если есть несколько петель (рядом или одна над другой), то их аналоги в БНФ будут разделятся знаком |.
Поясним это все примером диаграммы из трех строк (трех рисунков), описывающей идентификатор (грамматику идентификатора). Приведем сперва форму Бэкуса-Наура для этого идентификатора, отличающуюся, кстати, от уже приведенной выше. Она записана без использования скобок.
Теперь – диаграмма из 3-х строк:
Отметим, что третью строку диаграммы можно нарисовать и так:
На мой взгляд, принцип построения диаграмм Вирта достаточно понятен. Хотя, возможно, что-то из теории я и упустил, поскольку изучал этот материал по довольно отрывочной информации.
Взаимное соответствие между формой Бэкуса-Наура и программой (то-есть программирование транслятора по заданной БНФ).
Теперь мы подходим к самому главному моменту. Как, имея форму Бэкуса-Наура, составить программу? Допустим, форму, соответствующую некоторому языку (языку арифметических формул, например), мы составили.
Правила соответствия БНФ- Program такие:
1)Каждому терминалу, стоящему слева от «:=» (по крайней мере, тому, который может состоять из нескольких символов – такие мы брали в угловые скобки), соответствует функция в общей программе. То-есть, уточняю, «мелким» терминалам (таким как знак сложения, допустим, или цифра) функцию можно не сопоставлять. Но таким, как , , — соответствующую функцию сопоставлять нужно.
2)Каково же будет «наполнение» этих функций? То-есть их внутренняя начинка? Когда мы идем по правой части строки формы (то-есть правее от «:=») слева направо и встречаем «крупный» терминал (, ), мы записываем внутри нашей функции (которую сейчас мы заполняем операторами) соответствующий вызов функции. Далее – фигурным скобкам (повторению ноль или более раз) будет соответствовать оператор цикла while . Условием этого цикла скорее всего будет наличие знака математической операции, который стоит первым в скобке (опять таки вероятнее всего). Если же скобки квадратные (действие ноль или один раз), то им соответствует условный оператор if .
Если в правой части строки БНФ есть ряд частей, разделенных вертикальной палочкой (| — знак альтернативы), то каждой такой части должен соответствовать свой участок кода внутри нашей функции. Реализовать такую «архитектуру» можно с помощью if или if — else . Можно применять и другие способы
3)Наша программа, которую мы транслируем, должна выполнять некоторую полезную работу, например складывать и перемножать числа, чтобы получить конечное значение формулы. Насчет этого «пункта» в формах Бэкуса-Наура не говорится ничего. Но в программе-трансляторе эти куски кода должны быть обязательно. Можно дать совет вставлять их и испытывать методом проб и ошибок.
4)Еще важный пункт – при движении по правой части строки мы переходим от одного терминала к другому. Внутри функции этому соответствует вызов сканера для получения следующей лексемы после очередного «внутреннего» вызова функции. Но нужно учесть, что некоторые вызовы сканера может оказаться удобным «прятать» внутри вызываемых внутренних функций, а не в теле самой функции (которую мы пишем в данный момент). Итак, движению слева направо (по правой части строки) от одного терминала к другому соответствуют вызовы сканера в программе.
Уточняю – сканер это функция или подпрограмма (функция программы-транслятора), которая просматривает весь текст программы (транслируемой) и делит его на так называемые лексемы. Лексема – это число, или имя переменной, или знак операции, или название оператора ( if , while ), или что другое (имя функции например). Обычно вызов сканера «поставляет» очередную лексему в программе.
Пример соответствия строки БНФ и функции (язык Си):
/* Обратите внимание на соответствие < addop >и проверки на наличие знака + в условии оператора цикла */
NextLexema( ); /* Вызов сканера */
Кстати, вышеприведенные рассуждения относятся не только к программам на языке Си, но и к любым языкам, поддерживающим рекурсивные функции (а также операторы цикла и условные операторы, естественно).
Простая форма Бэкуса — Наура (БНФ)
Блог
Автор Михаил Миронов На чтение 4 мин Обновлено 09.07.2023
Краткий обзор, отвечающий на вопросы: Что это? Где используется? Правила написания и примеры использования.
Backus–Naur form или Backus normal form (BNF) это формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик, обычно используется для описания синтаксиса языков программирования, форматов документов, наборов инструкций и протоколов связи. Применяются везде, где необходимо точное описание синтаксиса: например, в официальных спецификациях, руководствах и учебниках.
Так же существует ещё и расширенная форма Бэкуса — Наура, отличающаяся более ёмкими конструкциями.
Термины:
- Терминалили терминальный символ — объект, непосредственно присутствующий в словах языка, соответствующего грамматике, и имеющий конкретное, неизменяемое значение.
- Нетерминалили нетерминальный символ — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
БНФ-конструкция определяет конечное число нетерминалов (символов) и определяет правила замены символа на какую-то последовательность терминалов (букв) и символов.
За процесс построения цепочки букв можно проследить поэтапно:
- Изначально имеется только один символ. Обычно символы представляются в виде некого названия заключенного в угловые скобки.
- Затем этот символ заменяется некоторой последовательностью букв и символов, согласно одному из описанных правил.
- Затем процесс повторяется (на каждом шаге один из символов заменяется на последовательность, согласно правилу).
В конце концов, получается цепочка, состоящая из букв и не содержащая символов.
Запись правила разбита на две части разделенных символом определения ::= или иногда вместо него используют -> . В левой части содержится определяемый символ, а справа последовательность из букв и символов. В описании правила в правой части может использоваться оператор выбора “|” обеспечивающий логическое ИЛИ. В описании правила может применяться рекурсия.
Существует множество вариантов улучшенного синтаксиса, в частности в расширенной форме Бэкуса — Наура (РБНФ) помимо оператора выбора можно использовать условное вхождение, группировку или повторение.
Примеры конструкций БНФ
Общий вид конструкции.
БНФ-конструкция правильной скобочной последовательности.
Конструкция состоит только из одного правила. Согласно этому правилу символ может быть заменена на пустое место, либо на символ обрамленный круглыми скобками, либо на два симола идущих подряд.
Синтаксис БНФ представленный БНФ-конструкцией (используется латиница)
::= | ::= " ">" "::=" ::= " " | "" ::= | "|" ::= | ::= | ::= | " ">" ::= '"' '"' | "'" "'" ::= "" | ::= "" | ::= | | ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ::= "|" | " " | "-" | "!" | "#" | "$" | "%" | "&" | "(" | ")" | "*" | "+" | "," | "-" | "." | "/" | ":" | ";" | "" | "?" | "@" | "[" | "\" | "]" | "^" | "_" | "`" | "" | "~" ::= | "'" ::= | '"' ::= | ::= | | "-"