Проверка оператора "break" с помощью синтаксического анализатора с рекурсивным спуском - PullRequest
Новая
       11

Проверка оператора "break" с помощью синтаксического анализатора с рекурсивным спуском

0 голосов
/ 08 мая 2018

В Создание интерпретаторов , мы реализуем небольшой язык программирования с использованием парсера рекурсивного спуска. Среди прочего есть следующие утверждения: 

statement → exprStmt
          | ifStmt
          | printStmt
          | whileStmt
          | block ;

block     → "{" declaration* "}" ;
whileStmt → "while" "(" expression ")" statement ;
ifStmt    → "if" "(" expression ")" statement ( "else" statement )? ;

Одним из упражнений является добавление break оператора к языку. Кроме того, это должно быть синтаксической ошибкой, чтобы этот оператор находился вне цикла. Естественно, он может появляться внутри других блоков, if операторов и т. Д., Если они находятся внутри цикла.

Моим первым подходом было создание нового правила, whileBody, для принятия break: 

## FIRST TRY
statement → exprStmt
          | ifStmt
          | printStmt
          | whileStmt
          | block ;

block     → "{" declaration* "}" ;
whileStmt → "while" "(" expression ")" whileBody ;
whileBody → statement
          | break ;
break     →  "break" ";" ;
ifStmt    → "if" "(" expression ")" statement ( "else" statement )? ;

Но мы должны принять break внутри вложенных циклов, if условных выражений и т. Д. Я могу себе представить, что мне нужно новое правило для блоков и условных выражений, которые принимают break: 

## SECOND TRY
statement → exprStmt
          | ifStmt
          | printStmt
          | whileStmt
          | block ;

block     → "{" declaration* "}" ;
whileStmt → "while" "(" expression ")" whileBody ;
whileBody → statement
          | break
          | whileBlock
          | whileIfStmt
whileBlock→  "{" (declaration | break)* "}" ;
whileIfStmt    → "if" "(" expression ")" whileBody ( "else" whileBody )? ;  
break     →  "break" ";"
ifStmt    → "if" "(" expression ")" statement ( "else" statement )? ;

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

Я искал вдохновение в спецификациях C и Java BNF. Очевидно, что ни одна из этих спецификаций не запрещает внешний цикл break. Я предполагаю, что их парсеры имеют специальный код, чтобы предотвратить это. Итак, я последовал их примеру и добавил код в анализатор, чтобы предотвратить break внешние циклы .

TL; DR

Мои вопросы:

  1. Будет ли подход моей второй попытки вообще работать? Другими словами, может ли анализатор рекурсивного спуска обработать оператор break, который появляется только внутри циклов?
  2. Есть ли более практичный способ испечь команду break в спецификации синтаксиса?
  3. Или стандартный способ действительно состоит в том, чтобы изменить синтаксический анализатор, чтобы предотвратить разрывы внешних циклов при разборе?

Ответы [ 2 ]

0 голосов
/ 19 июня 2018

Грамматики атрибутов хороши в таких вещах. Определите унаследованный атрибут (я назову его LC для подсчета цикла). Нетерминал 'program' передает LC = 0 своим дочерним элементам; циклы передают LC = $ LC + 1 своим детям; все другие конструкции передают LC = $ LC своим детям. Сделайте правило синтаксически допустимым для break, только если $ LC> 0.

Не существует стандартного синтаксиса для грамматик атрибутов или для использования значений атрибутов в охранниках (как я предлагаю для 'break'), но при использовании грамматической нотации с определенным предложением Prolog ваша грамматика может выглядеть примерно так: Я добавил несколько примечаний к нотации DCG, на случай, если прошло слишком много времени с тех пор, как вы их использовали. 

/* nt(X) means, roughly, pass the value X as an inherited attribute. 
** In a recursive-descent system, it can be passed as a parameter.
** N.B. in definite-clause grammars, semicolon separates alternatives,
** and full stop ends a rule.  
*/

/* DCD doesn't have regular-right-part rules, so we have to  
** handle repetition via recursion.
*/ 
program -->
    statement(0);
    statement(0), program.

statement(LC) -->
    exprStmt(LC);
    ifStmt(LC);
    printStmt(LC);
    whileStmt(LC);
    block(LC);
    break(LC).

block(LC) -->
    "{", star-declaration(LC), "}".

/* The notation [] denotes the empty list, and matches zero
** tokens in the input.  
*/
star-declaration(LC) -->
    [];
    declaration(LC), star-declaration(LC).

/* On the RHS of a rule, braces { ... } contain Prolog code.  Here,  
** the code "LC2 is LC + 1" adds 1 to LC and binds LC2 to that value.
*/ 
whileStmt(LC) -->
    { LC2 is LC + 1 }, "while", "(", expression(LC2), ")", statement(LC2).

ifStmt(LC) --> "if", "(", expression(LC), ")", statement(LC), opt-else(LC).

opt-else(LC) -->
    "else", statement(LC);
    [].

/* The definition of break checks the value of the loop count:
** "LC > 0" succeeds if LC is greater than zero, and allows the
** parse to succeed.  If LC is not greater than zero, the expression
** fails.  And since there is no other rule for 'break', any attempt
** to parse a 'break' rule when LC = 0 will fail.
*/
break(LC) --> { LC > 0 }, "break", ";".

Хорошие введения в атрибутивные грамматики можно найти в Grune and Jacobs, Методы синтаксического анализа и в томах Springer. . Журдан) и 545 ( Грамматики атрибутов, приложения и системы , изд. Х. Альблас и Б. Меличар.

Техника дублирования некоторых произведений для различения двух ситуаций (я в цикле? Или нет?), Как показано в ответе @rici, может рассматриваться как способ вставить логический атрибут в не Терминальные имена.

0 голосов
/ 08 мая 2018
  1. Будет ли подход моей второй попытки вообще работать? Другими словами, может ли анализатор рекурсивного спуска обработать оператор break, который появляется только внутри циклов?

Конечно. Но вам нужно много дублирования. Поскольку while - не единственная конструкция цикла, я использовал другой способ описания альтернатив, который заключается в добавлении _B к имени нетерминалов, которые могут включать break операторов. 

declaration    → varDecl
               | statement
declaration_B  → varDecl
               | statement_B
statement      → exprStmt
               | ifStmt
               | printStmt
               | whileStmt
               | block
statement_B    → exprStmt
               | printStmt
               | whileStmt
               | breakStmt
               | ifStmt_B
               | block_B
breakStmt      → "break" ";"
ifStmt         → "if" "(" expression ")" statement ( "else" statement )?
ifStmt_B       → "if" "(" expression ")" statement_B ( "else" statement_B )?
whileStmt      → "while" "(" expression ")" statement_B ;
block          → "{" declaration* "}"
block_B        → "{" declaration_B* "}"

Не все типы операторов должны дублироваться. Несоставные операторы, такие как exprStmt, не делают этого, поскольку они не могут включать оператор break (или любой другой тип оператора). И statement, который является целью оператора цикла, такого как whileStmt, всегда может включать break, независимо от того, был ли while внутри цикла или нет.

  1. Есть ли более практичный способ испечь команду break в спецификации синтаксиса?

Нет, если в вашей синтаксической спецификации нет макросов-маркеров, как в спецификации, используемой для описания ECMAScript.

  1. Есть ли другой способ сделать это?

Поскольку это анализатор нисходящего (рекурсивного спуска), довольно просто обработать это условие при выполнении синтаксического анализатора. Вам просто нужно добавить аргумент для каждой (или многих) функций синтаксического анализа, который указывает, возможен ли разрыв или нет. Любая функция синтаксического анализа, вызванная whileStmt, установит этот аргумент в True (или перечисление, указывающее, что разрыв возможен), в то время как другие типы операторов просто передадут параметр, а функция синтаксического анализа верхнего уровня установит аргумент в False. Реализация breakStmt будет просто возвращать ошибку, если она вызывается с False.

...