Как представить вертикальное выравнивание синтаксиса кода с помощью BNF, EBNF и т. д.?

Как сказать, что (в BNF, EBNF и т. д.) любые две или более буквы расположены в одном и том же вертикальном выравнивании

например, в python 2.x у нас есть то, что мы называем indentation.

def hello():
    print "hello," 
    print "world"

hello()

Примечание, буква p (вторая строка) расположена в том же вертикальном положении, что и буква p (третья строка).

Еще пример (в уценке):

MyHeader
========
topic
-----

Примечание M и первый = расположены в одном вертикальном выравнивании (также r и последний =, t и первый -, c и последний -)

Мой вопрос: Как представить это вертикальное выравнивание букв, используя BNF, EBNF и т. д.?

Дополнительное примечание: Моя цель этого вопроса заключается в поиске метода представления для представления вертикального выравнивания кода, а не просто в том, чтобы знать, как написать BNF или EBNF Python или Markdown.


syntax indentation ebnf bnf vertical-text
person fronthem    schedule 05.01.2015    source источник
comment
Учитывая, что BNF может представлять контекстно-свободные грамматики, у вас могут возникнуть некоторые трудности с их использованием для представления грамматики, которая на самом деле не является контекстно-свободной... python не является полностью контекстной. бесплатно; части его есть, но языка в целом нет.   -  person twalberg    schedule 05.01.2015
comment
Любыми другими способами, которыми вы можете ответить мне ниже, я просто хочу решение, которое может представлять вертикальное выравнивание кода.   -  person fronthem    schedule 05.01.2015

Ответы (1)


arrow_upward
10
arrow_downward

Вы можете проанализировать язык, чувствительный к отступам (например, Python или Haskell), с помощью небольшой хитрости, которая хорошо описана в главе справочника по языку Python на странице лексический анализ. Как описано выше, лексический анализатор превращает начальные пробелы в токены INDENT и DEDENT [Примечание 1], которые затем используются в грамматике Python простым способом. Вот небольшой отрывок:

suite         ::=  stmt_list NEWLINE | NEWLINE INDENT statement+ DEDENT
statement     ::=  stmt_list NEWLINE | compound_stmt
stmt_list     ::=  simple_stmt (";" simple_stmt)* [";"]
while_stmt    ::=  "while" expression ":" suite ["else" ":" suite]

Итак, если вы готовы описать (или сослаться) на алгоритм лексического анализа, БНФ прост.

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

стандарт ISO EBNF (доступен бесплатный PDF-файл) позволяет включить расширения, которые могут потребоваться пользователю: Special-sequence, который представляет собой любой текст, не содержащий ?, окруженный с обеих сторон ?. Таким образом, вы можете злоупотреблять обозначениями, включая [Примечание 2]:

DEDENT = ? See section 2.1.8 of https://docs.python.org/3.3/reference/ ? ;

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

Стоит отметить, что сам EBNF использует специальную последовательность для определения одного из своих продуктов:

(* see 4.7 *) syntactic exception
   = ? a syntactic-factor that could be replaced
       by a syntactic-factor containing no
       meta-identifiers
     ? ;

Примечания

  1. Лексический анализатор также преобразует некоторые физические символы новой строки в токены NEWLINE, в то время как другие символы новой строки исчезают.

  2. EBNF обычно использует синтаксис =, а не ::= для производства, и настаивает на том, чтобы они заканчивались ;. Комментарии заключены между (* и *).

person rici    schedule 06.01.2015
comment
Отличный ответ! - person rns; 06.01.2015
comment
Я не совсем понял... значит ли это, что результат предварительной обработки с помощью лексического анализатора может быть описан контекстно-свободной грамматикой? а того, что делает сам лексический анализатор, быть не может? - person Anentropic; 26.09.2018
comment
@anentropic: вот что это значит. Лексический анализатор должен иметь стек позиций отступов, и вы не можете представить такой стек в CFG. - person rici; 26.09.2018