两周自制脚本语言-第5天 设计语法分析器

第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类的方法

两周自制脚本语言-第5天 设计语法分析器

语法规则的处理

paren : "(" expr ")"

转换为Java语言后将得到下面的代码

Parser paren = rule().sep("(").ast(expr).sep(")");

两周自制脚本语言-第5天 设计语法分析器

factor : "-" primary | primary

对应factor字段的定义如下

Parser factor = rule().or(rule().sep("-").ast(primary), primary);

两周自制脚本语言-第5天 设计语法分析器

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方法将在成功执行语法分析后以抽象语法树的形式返回分析结果。

两周自制脚本语言-第5天 设计语法分析器

语法规则

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

两周自制脚本语言-第5天 设计语法分析器

特殊的规定:如果子节点只有一个,Parser库将不会另外创建一个额外的节点。

两周自制脚本语言-第5天 设计语法分析器

规定不适用于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 通过在表达能力上做的妥协换取在某一领域内的高效

参考

https://www.cnblogs.com/feng9…

https://zhuanlan.zhihu.com/p/…

原文 

https://segmentfault.com/a/1190000021612893

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 两周自制脚本语言-第5天 设计语法分析器

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址