c++ - 如何构建解析树？

Question

已找到 C++ BNF 和下一行

selection-statement:
    if ( condition ) statement
    if ( condition ) statement else statement

现在正在尝试编写解析器。需要构建解析树。输入时我有 BNF 和源文件。但我陷入了如何向我的解析器指出如果条件评估为true，那么它需要执行第一个语句，否则else block 会怎样？谢谢。

Answer 1

条件语句具有简单的递归结构。相应的递归下降解析器具有类似的简单递归结构。抽象地，内部条件解析如下:

<cond> -> if <expression> then <statement> [else <statement>]

cond :
  a = parse expression
  b = parse statement
  if is_else(token)
    then c = parse statement
         return conditional(a,b,c)
    else return conditional(a,b)

在您的示例中，条件语句包含条件 block ，其中最后一个包含 else 子句。假设标记化的输入序列具有这种形式，并且在词法分析期间检测到语法错误，则外部条件解析如下:

<conditional> -> selection_statement: {<cond>} <cond>

conditional :
  b = new block
  while (iscond(next))
    s = parse cond
    b = insert(s,b)
  return b

当然，实际的实现会更加详细和繁琐。然而，前面概述了从标记化输入序列构建具有所需形式的条件语句的解析树。

我刚刚意识到您正在谈论评估抽象语法树。评估条件语句的函数的结构与解析条件语句的函数类似。抽象地说，

cond(input) :
  a = evaluate(if_part(input))
  if is_true(a)
    then evaluate(then_part(input))
    else if(is_else(input))
           then evaluate(else_part(input))
           else return

为了确定要计算条件的哪一部分，您必须首先将条件的“if”部分计算为 bool 值。如果 bool 值为“true”，则评估条件的“then”部分。如果 bool 值为“false”，则评估条件的“else”部分。如果没有“其他”部分，就没有什么可评价的。当然，实现会比上面更详细。