Java中的递归下降解析器

Question

我想说这是我的第三年编程语言类的家庭作业，我正在寻找一些帮助。我的任务写着：

截止日期：2013年2月22日下午11时55
投稿方式：请上传以下到CMS。

1.源代码
2.你的程序，包括你使用

你喜欢写递归下降解析器解析由产生的语言使用任何编程语言输入文件的执行的屏幕截图遵循EBNF描述。解析器应该检测输入程序是否有任何语法错误。它不需要指定错误的位置和位置。

<program>  begin <stmt_list> end 
<stmt_list>  <stmt> {;<stmt_list>} 
<stmt>  <assign_stmt> | <while_stmt> 
<assign_stmt>  <var> = <expr> 
<var>  identifier (An identifier is a string that begins with a letter followed by 0  or more letters and digits) 
<expr>  <var> { (+|-) <var>}   
<while_stmt>  while (<logic_expr>) <stmt> 
<logic_expr> ® <var> (< | >) <var> (Assume that logic expressions have only less than  or greater than operators) 

，看起来滑稽的符号只是指着右箭头。

我现在的问题更符合逻辑，那就是编程：在我第一次尝试时，我读完整个输入程序，将其保存为一个字符串，然后解析该字符串并将每个符号转换为终端，expr ，或者你有什么。

我终于发现这种方式是行不通的，因为答：我不认为它是RDP，B：很多非终端是由多于一个语句组成的。

我放弃了这种方法，并决定在浪费更多时间进行编程之前，我会把所有东西都伪装出来。我的新想法是为每个非终结符号制作1个方法，并且只用符号解析输入的字符串符号，希望在这些方法之间。这种方法似乎很合理，但是当我开始编写伪代码时，我非常迷茫，并且对于我需要做什么感到困惑。 我将如何完成此代码？

这里是RDP一些伪代码：

intputString; 

public void parseProgram (Symbol.typeIsProgram) { 
    if getNextSymbol == "begin" { 
     if (intputString.substring (inputString.length()-3, 
       inputString.length()) == "end") { 
      Symbol stmt_lsit = new Symbol (intputString) 
      parseStmt_list(stmt_list);    
     } else { 
      Out "error, prog must end with end" 
     } 
    } else { 
     Out "error, prog must begin with begin" 
    } 
} 

public void parseStmt_list (Stmbol.typeIsStmt_list) { 
    symbol = getNextSymbol; 
    if (Symbol.typeIsVar) { 
     parseVar(symbol) 
    } else if (Symbol.typeIsWhile) { 
     // weve only capture if the first word return is a while, we dont have the whole while statement yet 
     ParseWhile_stmt(symbol) 
    } else { } 
} 

public void parseStmt() { } 
public void parseAssign_stmt() { } 
public void parseVar() { } 
public void parseExpr() { } 
public void parseWhile_stmt() { } 
public void parseLogic_expr() { } 

public Symbol getNextSymbol() { 
    //returns the next symbol in input string and removes it from the input string 
} 

只是一个供参考的样本输入程序为我的解析器会。

begin 
total = var1 + var2; 
while (var1 < var2) 
while (var3 > var4) 
var2 = var2 - var1 
end 

Answer 1

解析器代码的结构应该类似于语言语法的结构。 例如

<program> ::= begin <stmt_list> end 

将转化为类似

function parse_program() { 
    parse_begin(); 
    repeat parse_stmt(); 
    parse_end(); 
} 

您可能希望不要与结构（语法分析器）的解析混淆令牌处理（扫描仪）。

我会去异常处理，而不是if/else结构的错误处理。 您可能想要跟踪源（扫描仪）部件的位置，以显示正确的错误消息。请询问扫描仪的状态。

幸运的是，该任务似乎不需要冲突解决方案，因此您的递归体面应该可以正常工作。有趣的部分是其中的

<while_stmt> ::= while (<logic_expr>) <stmt> 

解析到头来你会打电话给parse_stmt()递归。这就是递归下降解析的全部想法。

Answer 2

1）标记化

首先将输入分解为标记。在这种情况下，每个标识符和操作符和文字。列出所有输入令牌的大名单。一旦你有令牌，你就可以开始解析。将令牌设置为链接列表，以便您可以说Token.Next读取下一个令牌或Token.Next.Next以读取前面的2个令牌。在最后放置一堆EOF标记，以便永远不会跳过它。

2）解析

解析就像你已经。所以，而不是思考符号思考令牌。 Parse Statements列表是一个while循环，它保持分析语句直到结束。

对于解析声明

public void parseStmt() 
{ 
    if (Token.kind == KEYWORD && Token.id == kw_while) { 
    return ParseWhileStatement(); 
    } 
    else { 
    return ParseAssignStatement(); 
    } 
} 

解析while语句将循环回解析的语句，因此它将“递归下降”回解析的语句，产生嵌套while循环等等

解析该赋值语句非常相似。分析左侧，然后右侧。你需要一堆功能....

这里的节点是一个Ast节点。抽象语法树。

东西一样......

class Node { 

} 
class OpNode { 
    OpNode Lhs; 
    OpNode Rhs; 
} 
class MultiplyNode : OpNode { 
    MultiplyNode(byref Token tok, OpNode Left, OpNode right) { 
    tok = tok.Next; 
    Lhs = left; 
    Rhs = right; 
    } 
} 




Node ParseSimpleExp() { 
    if (Token.kind == Identifier) { 
    Node n = new IdentNode; 
    NextToken(); 
    return n; 
    } 
    if (Token.kind == Number) { 
    Node n = new NumberNode; 
    NextToken(); 
    return n; 
    } 
} 


// In these examples move the token to next token when you create the new nodes 
Node ParseMulExp() { 
    Node n = ParseSimpleExp(); 
    while (1) { 
    if (Token.Kind == Multiply) { 
     n = new MultiplyNode(Token,n,ParseSimpleExp()); 
     continue; 
    } 
    if (Token.Kind == Divide) { 
     n = new DivideNode(Token,n,ParseSimpleExp()); 
     continue; 
    } 
    return n; 
} 
} 

Node ParseAddExp() { 
    Node n = ParseMulExp(); 
    while (1) { 
    if (Token.Kind == Add) { 
     n = new AddNode(Token,n,ParseMulExp()); 
     continue; 
    } 
    if (Token.Kind == Subtract) { 
     n = new SubtractNode(Token,n,ParseMulExp()); 
     continue; 
    } 
    return n; 
    } 
} 


Node ParseAssignStatement() { 
    Node n = ParseAddExp(); 
    if (Token.kind == ASSIGN) { 
    return new AssignStatement(Token,n,ParseAddExp()); 
    } 
} 

如果你跟随你可以看到优先级规则如何，然后在每一个目标递归到达的逻辑。解析表达式并从分配开始不是循环。这就像这里所示。显然这很简单，但它显示了这项技术。

所以RDP是通过查看当前令牌然后跳转到某个函数来处理令牌引起的。自然这可以回到相同的功能，因此是递归的。如果你看一下ParseSimpleExp函数，那么你可以看到这是一个处理加括号表达式的好地方。 parens表达式将导致递归回到简单的exp，并且可能使所有其他像mul和add一样。

Answer 3

根据这个特定的赋值，可以以函数方式使用字符串处理。

试试这个算法：

1. 检查，该行开始begin与end
2. 结束，如果是 - 分裂剩余字符串;并执行以下步骤为每个部分（声明）
3. 检查语句是否包含=或while子串
4. 分配检查您可以将输入与+或-并且对于每个部分检查变量条件（字母数字内容）
5. 用于在 - 检查(和)递归处理括号之间和之后
6. 最后，对于由子串<或>拆分逻辑表达式，和两个串检查零件是否是变量（字母数字）

也许，这不是非常灵活的解决方案，但正如我所看到的那样，您的任务是可以接受的。

编辑：

我发现有趣的任务，并试图写一个完整的解决方案。

public enum Parser { 
PROGRAM { 
    void parse(String s) throws ParseException { 
     s = s.trim(); 
     if (s.startsWith("begin") && s.endsWith("end")) { 
      STATEMENT_LIST.parse(s.substring(5, s.length() - 3)); 
     } else { 
      throw new ParseException("Illegal begin/end"); 
     } 
    } 
}, 

STATEMENT_LIST { 
    void parse(String s) throws ParseException { 
     String[] parts = s.trim().split(";"); 
     for (String part : parts) { 
      STATEMENT.parse(part.trim()); 
     } 
    } 
}, 

STATEMENT { 
    void parse(String s) throws ParseException { 
     if (s.startsWith("while")) { 
      WHILE.parse(s.substring(5)); 
     } else if (s.contains("=")) { 
      ASSIGNMENT.parse(s); 
     } else { 
      throw new ParseException("Illegal statement: " + s); 
     } 
    } 
}, 

WHILE { 
    void parse(String s) throws ParseException { 
     int i = s.indexOf("("); 
     int j = s.indexOf(")"); 
     if (i != -1 && j != -1) { 
      LOGICAL.parse(s.substring(i + 1, j).trim()); 
      STATEMENT.parse(s.substring(j + 1).trim()); 
     } else { 
      throw new ParseException("Illegal while: " + s); 
     } 
    } 
}, 

ASSIGNMENT { 
    void parse(String s) throws ParseException { 
     int i = s.indexOf("="); 
     if (i != -1) { 
      VARIABLE.parse(s.substring(0, i).trim()); 
      EXPRESSION.parse(s.substring(i + 1).trim()); 
     } 
    } 
}, 

EXPRESSION { 
    void parse(String s) throws ParseException { 
     String[] parts = s.split("\\+|-"); 
     for (String part : parts) { 
      VARIABLE.parse(part.trim()); 
     } 
    } 
}, 

LOGICAL { 
    void parse(String s) throws ParseException { 
     int i; 
     if (s.contains("<")) { 
      i = s.indexOf("<"); 
     } else if (s.contains(">")) { 
      i = s.indexOf(">"); 
     } else { 
      throw new ParseException("Illegal logical: " + s); 
     } 

     VARIABLE.parse(s.substring(0, i).trim()); 
     VARIABLE.parse(s.substring(i + 1).trim()); 
    } 
}, 

VARIABLE { 
    void parse(String s) throws ParseException { 
     if (!s.matches("^[a-zA-Z][a-zA-Z0-9]*$")) { 
      throw new ParseException("Illegal variable: " + s); 
     } 
    } 
}; 

abstract void parse(String s) throws ParseException; 

public static void main(String[] args) { 
    try { 
     PROGRAM.parse("begin \n" + 
       "total = var1 + var2; \n" + 
       "while (var1 < var2) \n" + 
       "while (var3 > var4)\n" + 
       "var2 = var2 - var1 \n" + 
       "end"); 
     System.out.println("OK"); 
    } catch (ParseException e) { 
     System.out.println(e.getMessage()); 
    } 
} 
} 

class ParseException extends Exception { 
public ParseException(String message) { 
    super(message); 
} 
}