5

我想先说这是我第三年编程语言课的家庭作业，我正在寻求一些帮助。我的作业内容如下：

截止日期：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 或具有你。

我最终发现这种方式行不通，因为，A：我不认为它是 RDP，B：许多非终端是由超过 1 个语句组成的。

我放弃了这种方法，并决定在我浪费更多时间编程之前，我会把所有东西都伪掉。我的新想法是为每个非终端符号创建 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
4

3 回答 3

7

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

试试这个算法：

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

也许，这不是非常灵活的解决方案，但我认为它可以满足您的任务。

编辑：

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

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);
}
}
于 2013-02-16T19:30:25.780 回答
4

1) 代币化

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

2) 解析

解析就像你已经拥有的一样。因此，不要考虑 Symbol 而是考虑 Token。Parse Statements 列表是一个 while 循环，它会一直解析语句直到结束。

解析语句

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

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

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

这里的 Node 是一个 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是通过查看当前token然后跳转到某个函数来处理token引起的。自然这可以返回到相同的函数，因此是递归的。如果您查看 ParseSimpleExp 函数，那么您会发现这是处理带括号的表达式的好地方。parens 表达式将导致递归回到简单的 exp 并可能所有其他表达式，如 mul 和 add。

于 2013-02-16T19:22:24.160 回答
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()递归调用。这就是递归下降解析的整个想法。

于 2013-02-16T19:17:47.377 回答