第5天 设计语法分析器
5.1 Stone语言的语法
代码清单 5.1 Stone 语言的语法定义
primary : "(" expr ")" | NUMBER | IDENTIFIER | STRING
factor : "-" primary | primary
expr : factor { OP factor }
block : "{" [ statement ] { (";" | EOL) [ statement ] } "}"
simple : expr
statement : "if" expr block [ "else" block ]
| "while" expr block
| simple
program : [ statement ] (";" | EOF)5.2 使用解析器和组合子
Parser库: 一种解析器组合子类型的库 工作是将BNF写成的语法规则改写成Java语言程序 在书中第十七章有详细解说
代码清单 5.2 Stone 语言的语法分析器BasicParser.java
//代码清单5.2 由代码清单5.1中列出的Stone语言语法转换而成的语法分析程序。
/*
A basic Parser for Stone grammatical analysis
*/
package stone;
import stone.Parser.Operators;
import stone.ast.*;
import java.util.HashSet;
import static stone.Parser.rule;
public class BasicParser {
HashSet<String> reserved = new HashSet<String>();
Operators operators = new Operators();
Parser expr0 = rule();
Parser primary = rule(PrimaryExpr.class)
.or(rule().sep("(").ast(expr0).sep(")"),
rule().number(NumberLiteral.class),
rule().identifier(Name.class, reserved),
rule().string(StringLiteral.class));
Parser factor = rule().or(rule(NegativeExpr.class).sep("-").ast(primary),
primary);
Parser expr = expr0.expression(BinaryExpr.class, factor, operators);
Parser statement0 = rule();
Parser block = rule(BlockStmnt.class)
.sep("{").option(statement0)
.repeat(rule().sep(";", Token.EOL).option(statement0))
.sep("}");
Parser simple = rule(PrimaryExpr.class).ast(expr);
Parser statement = statement0.or(
rule(IfStmnt.class).sep("if").ast(expr).ast(block)
.option(rule().sep("else").ast(block)),
rule(WhileStmnt.class).sep("while").ast(expr).ast(block),
simple);
Parser program = rule().or(statement, rule(NullStmnt.class))
.sep(";", Token.EOL);
public BasicParser() {
reserved.add(";");
reserved.add("}");
reserved.add(Token.EOL);
operators.add("=", 1, Operators.RIGHT);
operators.add("==", 2, Operators.LEFT);
operators.add(">", 2, Operators.LEFT);
operators.add("<", 2, Operators.LEFT);
operators.add("+", 3, Operators.LEFT);
operators.add("-", 3, Operators.LEFT);
operators.add("*", 4, Operators.LEFT);
operators.add("/", 4, Operators.LEFT);
operators.add("%", 4, Operators.LEFT);
}
public ASTree parse(Lexer lexer) throws ParseException {
return program.parse(lexer);
}
}Parser类与Operators类都是由库提供的类。
rule方法是Parser类中的一个static方法
primary字段的定义基于非终结符primary的语法规则。factor与block同理，都是相应的Java语言形式的语法规则。
终结符：不能单独出现在推导式左边的符号，也就是说终结符不能再进行
推导。非终结符： 不是终结符的都是非终结符。非终结符可理解为一个可拆分元素，而终结符是不可拆分的最小元素。
表5.1 Parser类的方法
语法规则的处理
paren : "(" expr ")"转换为Java语言后将得到下面的代码
Parser paren = rule().sep("(").ast(expr).sep(")");
factor : "-" primary | primary对应factor字段的定义如下
Parser factor = rule().or(rule().sep("-").ast(primary), primary);
expr : factor { OP factor }=>
Parser expr = expr0.expression(BinaryExpr.class, factor, operators);运算符表以Operators对象的形式保存，它是expression方法的第三个参数。
operators.add("=", 1, Operators.RIGHT);
// Operator.RIGHT 右结合
// Operator.LEFT 左结合 add方法的参数分别是用于表示运算符的字符串、它的优先级以及左右结合顺序。用于表示优先级的数字是一个从1开始的int类型数值，该值越大，优先级越高。
5.3 由语法分析器生成的抽象语法树
Parser对象的parse方法将在成功执行语法分析后以抽象语法树的形式返回分析结果。
语法规则
adder: NUMBER "+" NUMBER改写为Java语言
Parser adder = rule().number().token("+").number();以token添加 + 号
Parser adder = rule(BinaryExpr.class).number(NumberLiteral.class)
.token("+")
.number(NumberLiteral.class)使用sep向模式添加分隔符
Parser adder = rule().number().sep(“+”).number();ast方法向模式添加非终结符。
Parser eq = rule().ast(adder).token("==").ast(adder);
特殊的规定：如果子节点只有一个，Parser库将不会另外创建一个额外的节点。
规定不适用于rule方法的参数接收了一个类的情况
创建以NegativeExpr对象为根的子树
rule(NegativeExpr.class).sep("-").ast(primary)如果希望在rule方法接受参数时也应用这条特殊规则，需要想下面这样作为参数的类定义签名方法
public static ASTree create(List<ASTree> c) {
return c.size() == 1 ? c.get(0) : new PrimaryExpr(c);
}将非终结符progrm的语法规则改写成Java语言
program : [ statement ] ("," | EOF)Parser program = rule().or(statement, rule(NullStmnt.class))
.sep(";",Token.EOF);5.4 测试语法分析器
知识补充
什么是DSL
简单查询了DSL，发现还是挺重要的 有时间详细学习下
Wikipedia 对于 DSL 的定义A specialized computer language designed for a specific task.
为了解决某一类任务而专门设计的计算机语言。
DSL 是 Domain Specific Language 的缩写，中文翻译为领域特定语言（下简称 DSL）；而与 DSL 相对的就是 GPL.
GPL 是 General Purpose Language 的简称，即通用编程语言，也就是我们非常熟悉的 Objective-C、Java、Python 以及 C 语言等等。
DSL 通过在表达能力上做的妥协换取在某一领域内的高效
参考
