基于java的脚本语言hair的开发思路2-语法分析

2021-09-26 hair PV:

语法分析

在经过上一步的词法分析之后，我们已经将程序字符串分以上三种token。要想让程序运行起来，我们还必须将其构造为抽象语法树(Abstract Syntax Tree)。

它是用来表示程序结构的树形结构。其中树的节点也分为不同的类型。

具体的树节点类型后面介绍。

在我们得到AST之后，想要得到结果，就很简单了：我们只需要自底而上活得每个树节点的对应的值。其根节点的值就是最终的程序结果。

所以问题的关键是如何通过token队列来获得AST。这里我们首先引入BNF的概念。

BNF

BNF即巴科斯范式，其是一种描述语法的一种形式体系，是一种典型的元语言（相当于一种伪代码来描述语法规则）。其规则如下：

字符本身： “xxx” - 表示xxx字符本身。如：”function”表示匹配function字符。
[xxx]表示xxx模式出现0次或1次。
{xxx}表示xxx模式至少出现0次。
(xxx)表示括号内的模式为一个整体。
xxx|yyy表示匹配xxx或yyy模式。

后来BNF也做了很多扩展，我们这里仅使用以上5种模式。

整个匹配过程中包含两个过程，即：

创建匹配模式实例。
使用该模式匹配token串。

下面分别介绍：

创建匹配模式

对于一个匹配模式，就是一个Parser对象。其有两个成员变量：

elements：用于存放模式匹配的子模式，即子树模式结构。
factory：用于创建该模式对应的树节点。

接下来我们看看具体的创建代码：

其调用栈如下顺序：

第一步：通过rule()最外层API创建模式，其有两个重载，分别对应是否传入匹配到的树节点类型。

/*
 * Create an empty Parser without a parameter.
 */
public static Parser rule() { return rule(null); }

/*
 * Create a Parser with a ASTree parameter, caution that this Parser is a single node with the parameter.
 */
public static Parser rule(Class<? extends ASTree> clazz) {
    return new Parser(clazz);
}

Parser的构造方法，也有两个重载，其中第一个是用于构建模式树的根节点；而第二个适用于直接接受一个Parser并将其成员变量复制过来，其主要是用在maybe方法的实现中。

protected List<Element> elements;
protected Factory factory;

/*
 * This constructor is used for first create Parser.
 */
public Parser(Class<? extends ASTree> clazz) {
    reset(clazz);
}

/*
 * This constructor is used for chain call.
 */
protected Parser(Parser p) {
    elements = p.elements;
    factory = p.factory;
}

接下来的reset方法其实就是初始化（或者重置）Parser的成员：elements和factory

/*
 * Reset the parser, elements and factory are all need to be reset. 
 */
public Parser reset(Class<? extends ASTree> clazz) {
    elements = new ArrayList<Element>();
    factory = Factory.getForASTList(clazz);
    return this;
}

然后就是Factory对象的getForASTList静态方法，这里的两个方法比较重要，主要是如何来构建一个factory。首先会从外部传来的class来构建一个Factory。我们后面再看get方法，首先来分析f == null时的情况。

这里就直接通过new方法来构建一个新的factory，值得注意的是这里实现了本来是make0方法。

注意：这个方法是用在匹配token串，使用该方法创建对应的AST节点。

这里的逻辑是：判断传入的arg的长度是等于1。如果等于1则返回其第一个元素。否则的话就利用org返回一个新的ASTList。

protected static Factory getForASTList(Class<? extends ASTree> clazz) {
	/**
	 * Get the class with the ASTree class transferred by user.
	 */
    Factory f = get(clazz, List.class);
    
    /**
     * If user did not transferred the class,
     * we implement the make0 method and new a factory which make a normal ASTree object.
     */
    if (f == null)
        f = new Factory() {
            protected ASTree make0(Object arg) throws Exception {
                List<ASTree> results = (List<ASTree>)arg;
                if (results.size() == 1)
                    return results.get(0);
                else
                    return new ASTList(results);
            }
        };
    return f;
}

接下来我们来看get方法。这里主要是如何利用传入的class来构建这个factory。首先如果是没有传入class，则直接返回class。

如果class != null时，则会有两种情况：
1. 首先判断这个class有没有create方法（factoryName为字符串creatr），如果有的话就获取这个方法，然后实现了make0方法。
2. 其次判断是否有构造器，如果有的话，make0方法就会直接利用该构造函数来新建一个该对象。

protected static Factory get(Class<? extends ASTree> clazz,
                             Class<?> argType)
{
	/**
	 * If user transferred no class, get method return null.
	 */
    if (clazz == null)
        return null;
    try {
    	/**
    	 * Judge whether the class transferred by user has a "create" function.
    	 * If true, we just use the function to create the ASTree.
    	 */
        final Method m = clazz.getMethod(factoryName,
                                         new Class<?>[] { argType });
        return new Factory() {
            protected ASTree make0(Object arg) throws Exception {
                return (ASTree)m.invoke(null, arg);
            }
        };
    } catch (NoSuchMethodException e) {}
    
    /**
     * If the class has not a "create" function.
     * We judge whether the class has a constructor.
     * If true, we use the constructor to create the ASTree. 
     */
    try {
        final Constructor<? extends ASTree> c
            = clazz.getConstructor(argType);
        return new Factory() {
            protected ASTree make0(Object arg) throws Exception {
                return c.newInstance(arg);
            }
        };
    } catch (NoSuchMethodException e) {
        throw new RuntimeException(e);
    }
}

值得注意的是Parser对象还有很对方法用来对应BNF的规则：

number：用于向Parser的elements添加number型AToken（这里的AToken是在Parser中的内部类，属于模式AST类）。
identifier：用于向Parser的elements添加identifier型AToken。
string：用于向Parser的elements添加srting型AToken。
sep：用于向Parser的elements添加用于间隔型AToken，在BNF中对应字符串本身。
ast：用于向Parser的elements添加基本的树结构，常用于直接传递其他模式串作为子串。
or：用于向Parser的elements添加分支结构的树结构，对应BNF的|。
maybe：用于向Parser的elements添加可省略的模式。
option：用于向Parser的elements添加可省略的模式，对应BNF的[]。
repeat：用于向Parser的elements添加可重复的模式，对应BNF的{}。
expression：用于向Parser的elements添加以Express为树节点的模式。

下面是一个简单的模式的创建：

1	Parser classNew = rule(NewStmnt.class).sep("new").identifier(reserved).sep("(").option(args).sep(")");

其主要是匹配新建对象时的语法，如：

1	new Obj(111, 222)

可以看到rule首先接受了一个NewStmnt.class参数，这就意味着，当这个模式匹配成功时，其创建的节点是NewStmnt类型的。

然后sep("new")即匹配new这个字符。

identifier(reserved)即匹配保留字，即变量名等。

option(args)即表示匹配可以省略的arguments，这里的args也是在前面定义的一个模式，匹配诸如：222,"uuu"之类的参数模式。

匹配token串

在Parser中定义了诸多子类即模式节点，这些节点自己定义了parser方法用于解析对应的token是否匹配。

我们上面构建语法规则实际上形成了一个树，其节点就是之前定义在Parser内部的各种子类。

但其主要依然是一个递归的过程，首先会从队列中peek一个token（peek是不会让该token出队的），然后从匹配树的根部开始向下遍历，查找到其叶节点，然后匹配，如果通过则将调用其factory的make方法，来构建一个对应class的叶节点并且将其推入其elements中。

Parser结构

这里给出了一部分的结构（定义类的结构），我们模拟一下其解析过程：

class Myclass{
    a = 1
    constructor(param1){
        a = param1
    }
}

首先我们会通过Lexer会生成一个queue：

StrToken:”class”->IdToken:Myclass->StrToken:”a”->…

peek一个token，即第一个StrToken。
遍历树：从program->classDef->”class”，匹配成功。（若第一次没有匹配成功，将会在树上进行回溯）。
新建一个ClassDef对象的树节点。
接下来再peek一个token，即IdToken:Myclass
再从classDef的第二个节点开始匹配，发现也匹配成功。
创建一个Name树节点并将其加入刚才ClassDef的elements中。
后面也是如此，一次递归，失败就回溯；成功就继续匹配。

下面附上目前版本定义的规则（包括类，数组）：

package parser;
import static parser.Parser.rule;
import java.util.HashSet;
import parser.Parser.*;
import scanner.Lexer;
import token.Token;
import ast.*;
import entity.Function;
import exception.ParseException;

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

    
    /**
     * Function Parser
     */
    Parser param = rule().identifier(reserved);
    Parser params = rule(ParameterList.class).ast(param).repeat(rule().sep(",").ast(param));
    Parser paramList = rule().sep("(").maybe(params).sep(")");
    Parser function = rule(FunctionStmnt.class).sep("function").identifier(reserved).ast(paramList).ast(block);
    /**
     * InnerFunction Parser
     */
    Parser innerFunction = rule(InnerFunc.class).sep("func").ast(paramList).ast(block);
    Parser args = rule(Arguments.class).ast(expr).repeat(rule().sep(",").ast(expr));
//    Parser postfix = rule().sep("(").maybe(args).sep(")");
    Parser postfix = rule().or(rule(Dot.class).sep(".").identifier(reserved), 
    		rule().sep("(").ast(args).sep(")"),
    		rule(Squarebracket.class).sep("[").ast(expr).sep("]")
    		);
    Parser statement = statement0.or(
            rule(IfStmnt.class).sep("if").sep("(").ast(expr).sep(")").ast(block).option(rule().sep("else").ast(block)),
            rule(WhileStmnt.class).sep("while").sep("(").ast(expr).sep(")").ast(block),
            simple);
    
    /**
     * class Parser
     */
    Parser constructor = rule(Construtor.class).sep("constructor").ast(paramList).ast(block);
    /**
     * The order can not be changed. Or constructor maybe regard as simple parser.
     */
    Parser classEle = rule().or(constructor, function, simple);
    Parser classBody = rule(ClassBody.class).sep("{").option(classEle).
    		repeat(rule().sep(";", Token.EOL).option(classEle)).sep("}");
    Parser classDef = rule(ClassStmnt.class).sep("class").identifier(reserved).option(rule().sep("extends").identifier(reserved)).ast(classBody);
    Parser classNew = rule(NewStmnt.class).sep("new").identifier(reserved).sep("(").option(args).sep(")");
    
    /**
     * Array Parsers
     */
    Parser arrayDef = rule(ArrayStmnt.class).sep("[").ast(expr).repeat(rule().sep(",").ast(expr)).sep("]");
    
    /**
     * final program Parser.
     */
    Parser program = rule().or(classDef, statement, rule(NullStmnt.class))
            .sep(";", Token.EOL);
    
    public BasicParser() {
    	reserved.add(")");
        reserved.add(";");
        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);
        
        /**
         * avoid cycle reference, so we repair some Parser here.
         */
        primary.repeat(postfix);
        primary.insertChoice(innerFunction);
        primary.insertChoice(classNew);
        primary.insertChoice(arrayDef);
        simple.option(rule().sep(")").option(args).sep(")"));
    }
    public ASTree parse(Lexer lexer) throws ParseException {
        return program.parse(lexer);
    }
}

其中reserved即为保留字符，不会被识别为标识符等。

operators即为操作符，主要用在BinaryExpress即二元表达式中。

add函数的参数第一个是操作符，第二个是优先级，第三个是左先计算还是右先计算。