仿c语言自制编程语言笔记2

草,上周的词法分析,语句分析的笔记忘记保存没了….

表达式分析

javaCC将一个规则转化为一个方法,非终端符号直接调用方法,终端符号直接转化为TOKEN,所以一个方法中左侧不能调用方法本身否则会出现无限递归解析.
所以我们在解析表达式时,要考虑各个运算符的优先级,比如说:
1+2*3应该让乘法先解析,如果画成语法树的形式,那么低优先级的运算符号应该更加靠近根节点,按照自上而下的顺序来描述表达式的规则.

项的分析

表示项的符号是term().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//项的语法
term():{}
{
	LOOKAHEAD("(" type()) "(" type() ")" term()     //带强制类型转换的情况
	| unary()
}
//前置运算符语法
unary();{}
{
	"++"term()
	| "--"term()
	| "-" term()
	| "+" term()
	| "~" term()
	| "!" term()
	| "*" term()
	| "&" term()
	| LOOKAHEAD(3) <SIZEOF> "(" type() ")" //sizeof(类型)
	| <SIZEOF> unary()    //sizeof(表达式)
	| postfix()
}
//后置运算符语法

JavaCC的action

语法规则检查的同时需要生成语法树,,要借助action功能,一个简单的action的例子,是对结构体语法的扩充:

1
2
3
4
5
6
7
void defstruct():{}
{
	<STRUCT> name() member_list() ";"
	{
		System.out.println("发现了结构体!");
	}
}

在符号之后用一个大括号围起来的java代码,解析到该符号串时就会触发该代码.另外,开头要标注一个语义值,相当于返回值类型.
带有返回值的action:

1
2
3
4
5
6
7
String defstruct():{}
{
	<STRUCT> name() member_list() ";"
		{
			return "struct";
		}
}

还能获取终端符号或者非终端符号的语义值:

1
2
3
4
5
6
7
STRING name():
{
	Token tok;//定义临时变量
}
{
	tok=<INDENTIFIER> {return tok.image;}//获取<I>的语义值并返回其语义值(.image()方法返回字面量)
}

Token类中定义的属性,参见96页表格.
非终端符号的语义值获取唯一要主要的就是,终端符号的类型都是Token,非终端符号各不相同.
接下来就是将之前定义的语法全部扩充成有返回值的类型.

抽象语法树和节点

我们用一个基类Node来表示节点,然后继承得到各种特殊化的节点.所有节点类型的代码放在ast包内.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Node
	AST       	                //抽象语法树的根节点
	ExprNode                	//表达式节点
		AbstractAssignNode      //赋值
			AssignNode	//赋值表达式
			OpassignNode	//复合赋值表达式(+=,-=)
		AddressNode		//地址表达式(&x)
		BinaryOpNode		//二元运算表达式(x+y)
		CastNode		//类型转换
		CondExprNode			//条件运算表达式(a?b:c)
		FuncallNode			//函数调用表达式
		LHSNode				//能成为左值的表达式
			VariableNode		//变量表达式
			ArefNode		//数组
			DereferenceNode		//指针(*ptr)
			MemberNode		//字面量调用成员
			PtrMemberNode		//指针调用成员
		LiteralNode			//字面量
			IntegerLiteralNode	//整数字面量
			StringLiteralNode	//字符串
		SizeofExprNode			//sizeof表达式
		SizeofTypeNode			//计算类型的sizeof表达式
		UnaryOpNode			//一元运算表达式(-x,~x)
			UnaryArithmeticOpNode	//++和--运算符
				PrefixOpNode	//前置
				SuffixOpNode	//后置
	Slot					//结构体成员
	StmtNode				//表示语句的节点
		BlockNode			//程序块
		BreakNode			//break语句
		WhileNode
		DoWhileNode
		ForNode
		GotoNode
		LabelNode			//带标签的语句
		ReturnNode
		IfNode
		SwitchNode
		CaseNode
		ContinueNode
		ExprStmtNode			//能独立成语句的表达式
	TypeDefinition				//类型定义
		CompositeTypeDefinition		//结构体或联合体定义
			StructNode
			UnionNode
		TypedefNode			//类型重命名
	TypeNode				//类型的节点

其中比较重要的有:

  • AST 根节点
  • StmtNode 表示语句的节点的基类
  • ExprNode 表示表达式的节点的基类
  • TypeDefinition 定义类型的节点的基类

类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Type	//基本类型
	ArrayType
	IntegerType
	FunctionType
	VoidType
	PointerType
	NamedType	//抽象出的自命名的类型
		CompositeType		//组合类型
			UnionType
			StructType
		UserType	//typedef的类型
TypeRef
	ArrayTypeRef
	FunctionTypeRef
	IntegerTypeRef
	PointerTypeRef
	StructTypeRef
	UnionTypeRef
	UserTypeRef
	VoidTypeRef
TypeTable

ref类型的作用

TypeRef和Type的区别在与,前者是类型的名称,后者是类型的定义.比如解析struct s point;struct s {int x;},那么在定义struct s类型之前就遇到了其类型的变量,在寻找其type类型时找不到该类型的定义.
所以解决方法是先仅记录名称,然后在转换为Type对象.因此在Parser中生成的都是ref类型.

一元运算符的解析

如果有x->y->z这样的语法怎样解析呢?我们知道首先解析出token x,’->’成员调用符号和token y,那么状态转变为创造一个MemberNode节点,含有一个创造的调用表达式x,然后调用的对象是y,这样就完成了,继续解析出”->”和z,那么之前的MemberNode成为一个调用表达式,调用的对象为y,这样可以递归的进行.

左结合与右结合

1-2-3左结合,要用表达式expr1() ("-" expr1())*来解析,赋值语句x=y=z应该是右结合,所以需要expr():{}{term() "=" expr()}来解析.两种解析方法可以解析相同的语句,但是得到的语法树不同.

语句的语法树

关于location的调用,每个节点都有一个location方法,包含一个Location对象,记录了节点所在的文件名和行号.

函数定义的抽象语法树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
DefinedFunction defun():
{
	boolean priv;
	TypeRef ret;
	String name;
	Params pl;
	BlockNode body;
}
{
	priv=storage() ret=typeref() name=name()"("pl=params() ")" body=block()
		{
			TypeRef t=new FunctionTypeRef(ret,pl.parametersTypeRef());
			return new DefinedFunction(priv,new TypeNode(t),n,ps,body);
		}
}

一个函数包括是否是静态,返回类型,函数名,形参列表,函数体.
一个type是一个类型定义,一个typeref版本的只是这个类型的名字,所以我们在声明函数的时候要用ref,定义函数要返回一个type的子类.
可以说每种类型的type类中包含有typeref的信息.

声明列表的语法树

声明列表为top_defs(),返回一个Declarations类,用这个类来保存所有定义的类型.相当于一个容器来存储.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Declarations top_defs():
{
	Declarations decls=new Declarations();
	DefinedFunction defun;
	List<DefinedVariable> defvars;
	Constant defconst();
	StructNode	defstruct;
	UnionNode defunion;
	TypeDefNode deftype;
}
{
	(LOOKAHEAD(storage() typeref() <INDENTIFIER> "(")
	defun()//函数定义
		{decls.addDefun(defun);}
	| LOOKAHEAD(3) defvars=defvars()//变量定义
		{decls.addDefvars(defvars);
	| defconst=defconst()//常量定义
		{decls.addConstant(defconst);}
	| defstruct=defstruct()//结构体定义
		{decls.addDefstruct(defstruct);}
	| defunion=defunion()//联合体定义
		{decls.addDefunion(defunion);}
	| deftype=typedef()//类型别名
		{decls.addTypedef(deftype);}
	)*
		{
			return decls;
		}
}

表示程序整体的语法树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//一个编译单位,即一个文件的总体规则,import语句+函数或类型定义+文件结尾
AST compilation_unit():
{
	Token t;
	Declarations impdecls,decls;
}
{
	{
		t=getToken(1);//这个方法是JavaCC预定义在Parser类中的方法,可以得到一个token
	}
	impdecls=import_stmts() decls=top_defs() <EOF>
		{
			decls.add(impdecls); //两者先和并.
			return new AST(location(t),decls);
		}
}

声明类型的解析

import的文件中不含有定义,只含有变量,函数和类型的声明,函数和变量的用Undefinedxxx代替了DefinedXXX.其他的节点生成是一样的.
声明的语法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//多个import行,每个行用loader加载器加载得到一个Declarations,然后用impdecls合并所有的import.
Declarations import_stmts():
{
	Declarations impdecls=new Declaration();
	String libid;
}
{
	(libid=import_stmt()
		{
			try{
					Declarations decls=loader.loadLibary(libid,errorHandler);
					if(decls!=null){
						impdecls.add(decls);
						addKnownTypedefs(decls.typedefs());
					}
				}catch(CompileException e){
					throw new ParseException(e.getMessage());
		}
	)*
}
//一个import行的语法
String import_stmt():
{
	StringBuilder name;
	String s;
}
{
	<IMPORT> name(){ name.append(s);}
	( "." name(){name.append("."+s);} )* ";"
		{
			return name.toString();
		}
}
//解析声明文件的语法
Declarations declaration_file():
{
    Declarations impdecls, decls = new Declarations();
    UndefinedFunction funcdecl;
    UndefinedVariable vardecl;
    Constant defconst;
    StructNode defstruct;
    UnionNode defunion;
    TypedefNode typedef;
}
{
    impdecls=import_stmts()
        {
            decls.add(impdecls);
        }
    ( LOOKAHEAD(<EXTERN> typeref() <IDENTIFIER> "(")
      funcdecl=funcdecl()   { decls.addFuncdecl(funcdecl); }
    | vardecl=vardecl()     { decls.addVardecl(vardecl); }
    | defconst=defconst()   { decls.addConstant(defconst); }
    | defstruct=defstruct() { decls.addDefstruct(defstruct); }
    | defunion=defunion()   { decls.addDefunion(defunion); }
    | typedef=typedef()     { decls.addTypedef(typedef); }
    )*
    <EOF>
        {
            return decls;
        }
}

至此,基本上我们parser的解析器的部分就完成了,还有就是Parser类的一些工具方法,都是一些解字符串,转义字符和数值转字符的事情.

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码