使用递归下降分析器验证 "break" 语句

Question

在制作解释器中，我们使用递归下降解析器实现了一些编程语言。在许多其他事情中，它具有以下语句：

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 )? ;  

但是我们必须接受嵌套循环、if条件等中的break。我可以想象的是，我需要为接受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;博士

我的问题是：

1. 我第二次尝试的方法会奏效吗？换句话说，递归下降解析器是否可以处理仅在循环中出现的break语句？
2. 有没有更实用的方法在语法规范中烘焙break命令？
3. 或者标准方法确实是更改解析器以防止解析时在循环外中断？

Answer 1

属性语法擅长这种事情。 定义一个继承的属性(我称之为循环计数的 LC)。 "程序"非终端将 LC = 0 传递给其子项;循环将 LC = $LC + 1 传递给其子项;所有其他构造将 LC = $LC传递给其子构造。 仅当$LC> 0 时，才使"break"规则在语法上有效。

属性语法没有标准语法，或者在守卫中使用属性值(正如我建议的"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和Jacobs，解析技术和Springer卷Lecture Notes in Computer Science 461(属性语法及其应用*，编辑P. Deransart和M. Jourdan)和545(属性语法，应用程序和系统，编辑H. Alblas和B. Melichar)中找到。

复制一些作品以区分两种情况(我是否处于循环中？)的技术，如@rici的答案所示，可以被视为将布尔属性推送到非终端名称中的一种方式。

Answer 2

1. 我第二次尝试的方法会起作用吗？换句话说，递归下降解析器可以处理只出现在循环中的break语句吗？

确定。但是你需要大量的重复。由于while不是唯一的循环结构，因此我使用了另一种方法来描述替代方案，其中包括在可能包含break语句的非终端名称中添加_B。

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是否在循环内。

2. 有没有更实用的方法在语法规范中烘焙 break 命令？

除非你的语法规范有标记宏，比如用来描述 ECMAScript 的规范。

3. 有没有其他方法可以做到这一点？

由于这是一个自上而下(递归下降)解析器，因此在解析器的执行中处理此条件非常简单。您只需要为每个(或许多)解析函数添加一个参数，该参数指定是否可以中断。whileStmt调用的任何解析函数都会将该参数设置为True(或指示可以中断的枚举)，而其他语句类型只会传递参数，顶级解析函数会将参数设置为False。如果使用False调用breakStmt实现，则只会返回 失败。