时间戳

首页 > 解决方案 > 使用递归下降解析器验证“break”语句

parsing - 使用递归下降解析器验证“break”语句

问题描述

在Crafting Interpreters中，我们使用递归下降解析器实现了一种小编程语言。在许多其他方面，它具有以下声明：

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;博士

我的问题是：

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

标签： parsingsyntaxbreakformal-languagesrecursive-descent

解决方案

属性语法擅长这种事情。定义一个继承属性（我将其称为循环计数的 LC）。'program' 非终结符将 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, Parsing Techniques以及 Springer 卷 Lecture Notes in Computer Science 461 (Attribute Grammars and their Applications*, ed. P. Deransart 和 M. Jourdan) 和 545 ( Attribute Grammars, Applications, and Systems , ed. H. Alblas 和 B. Melichar。

正如@rici 的回答所示，为了区分两种情况（我是否处于循环中？）而复制一些产生式的技术可以被视为将布尔属性推入非终端名称的一种方式.

推荐阅读