如何建立解析树? [英] How to build parse tree?

问题描述

找到了C ++ BNF，接下来还有几行

Have found C++ BNF and there next lines

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

现在尝试编写解析器.需要建立解析树.输入时，我有BNF和源文件.但是我被困在如何指向解析器中，如果 condition 评估为true，那么它需要执行第一条语句，否则将阻塞?谢谢.

Now trying to write parser. Need to build parse tree. On input i have BNF and source file. But i'm stucked in how i can point my parser what if condition evaluated to true, then it need to execute first statement otherwise else block? Thanks.

推荐答案

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

Conditional statements have a simple recursive structure. The corresponding recursive descent parser has a similarly simple recursive structure. Abstractly, the interior conditionals are parsed as follows:

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

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

In your example, conditional statements contain blocks of conditionals the last of which contains an else clause. Assuming that the tokenized input sequence has this form and syntactic errors were detected during lexical analysis, the outer conditional is parsed as follows:

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

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

当然，实际的实现将更加详细和乏味.但是，前面概述了从标记化的输入序列中具有所需形式的条件语句的解析树的构造.

Of course, the actual implementation will be significantly more detailed and tedious. However, the preceding describes in outline the construction of a parse tree of a conditional statement having the required form from a tokenized input sequence.

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

I just realized you were talking about evaluating the abstract syntax tree. The structure of the function that evaluations a conditional statement is similar to the function that parses a conditional statement. Abstractly,

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"部分评估为布尔值.如果布尔值是"true"，则评估条件的"then"部分.如果布尔值是"false"，那么将评估条件的"else"部分.如果没有其他"部分，则没有任何可评估的内容.当然，实现将比上面更详细.

In order to determine which portion of the conditional to evaluate, you must first evalute the "if" part of the conditional to a Boolean value. If the Boolean value is "true," the "then" part of the conditional is evaluated. If the Boolean value is "false," then the "else" part of the conditional is evaluated. If there is no "else" part, there is nothing to evaluate. Of course, the implementation will be more detailed than the above.

这篇关于如何建立解析树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！