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

Question

已找到 C++ BNF 和下一行

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

现在正在尝试编写解析器。需要构建解析树。输入时我有 BNF 和源文件。但我一直纠结于如何指示我的解析器，如果 condition 评估为真，那么它需要执行第一条语句，否则会阻塞？谢谢。

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”部分。如果没有“else”部分，就没有什么可评估的。当然，具体实现会比上面更详细。