Пример BNF для грамматики языка, где уровень отступа определяет блок? - PullRequest
Новая
       21

Пример BNF для грамматики языка, где уровень отступа определяет блок?

0 голосов
/ 27 августа 2018

Я пытаюсь задокументировать синтаксис, который я использую в menuentries.conf, который является файлом конфигурации для пунктов меню, описывая синтаксис / грамматику с помощью обозначения, известного как расширенная форма Бэкуса-Наура EBNF ( BNF ) Этот menuentries.conf использует уровни отступов в качестве синтаксического компонента, как должно отображаться в этом примере: 

menu_entry_1
menu_entry_2
    menu_entry_2_submenu_entry_1
    menu_entry_2_submenu_entry_2
        menu_entry_2_submenu_entry_2_subsubmenu_1
        menu_entry_2_submenu_entry_2_subsubmenu_2
    menu_entry_2_submenu_entry_3
menu_entry_3
    menu_entry_3_submenu_entry_1

В приведенном выше примере каждая запись представлена ​​строкой, которая для примера подразумевает / указывает ее позицию. Кроме того, пример должен следовать этим правилам

  • каждый пункт меню представлен одной строкой (следовательно, пункты меню разделены NEWLINE)
  • пункты меню без любые отступы являются пунктами меню "верхнего уровня"
  • пункты меню с с отступом не"верхнего уровня", но дочерние записи для соответствующего пункта меню верхнего / верхнего уровня.

Моя попытка предоставить БНФ заключается в следующем: 

NEWLINE := '\n'
INDENTING := '    '
menu_entry_string := ('a'|'b'|....|'z'|'_'|'0'|'1'|...|'9')+
menu_entries := menu_entry (NEWLINE menuentry)*
menu_entry := menu_entry_string (NEWLINE INDENTING menu_entry)*
submenu_entry := INDENTING menu_entry_string
subsubmenu_entry := INDENTING INDENTING menu_entry_string

Мой вопрос, следовательно, касается моей неудовлетворенности рекурсивно объявленным понятием menu_entry и его избыточности с submenu_entry и subsubmenu_entry.
Зная, что python также использует отступы для создания понятия блоков, я подумал найти BNF / определение грамматики питонов (как здесь найдено: https://docs.python.org/3/reference/grammar.html), но оно оставляет соответствующие понятия INDENT и DEDENT вне грамматики.

Мой вопрос, следовательно: Как правильно использовать EBNF для описания грамматики / синтаксиса, в котором отступ используется в качестве блока группировки? В идеале был бы признателен небольшой пример (или, если возможно, исправление моей попытки).

В лучшем случае EBNF определит понятие nesting-level из block, которое будет: 1 для submenu_entry и 2 для subsubmenu_entry ....

1 Ответ

0 голосов
/ 28 августа 2018

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

  1. Спецификация Lexeme: определяет группы символов, которые представляют одну синтаксическую конструкцию (то есть значение токена или терминала)
  2. Спецификация грамматики: определяет допустимые комбинации синтаксических конструкций / токенов / терминальных значений, которые составляют нетерминальные значения, которые выражают, как язык может использоваться

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

Ниже приведена грамматика BNF, где STRING, NEWLINE, INDENT и DEDENT - все значения терминала, сгенерированные вашим лексером: 

start ::= list
        | list NEWLINE
        .

list  ::= entry
        | list entry
        .

entry ::= STRING NEWLINE
        | STRING NEWLINE INDENT list DEDENT
        .

Достаточно просто, верно? Я включил правило start, чтобы обеспечить допустимость любого файла, заканчивающегося маркером NEWLINE или DEDENT. Без этого файл, заканчивающийся токеном NEWLINE, которому не предшествовал токен STRING, был бы недействительным.

Я использовал BNF, но вы также можете легко использовать EBNF, если хотите. Дело в том, что лексер может понять, сколько пробелов используется для генерирования токена INDENT или DEDENT (или ошибки, если необходимо), и ваша грамматика должна просто указать, как работать с сгенерированными токенами.

...