nguyên lý ngôn ngữ lập trình nguyễn hứa phùng abstract syntax tree sinhvienzone com
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (72.03 KB, 6 trang )
C
o
e.
on
nZ
Dr. Nguyen Hua Phung
06, 2013
hV
ie
HCMC University of Technology, Viet Nam
in
m
Abstract Syntax Tree
/>
Dr. Nguyen Hua Phung
Abstract Syntax Tree
C
o
e.
Definition
◦ tree representation of the abtract syntax structure of
source code.
on
◦ differ from concrete syntax tree (parse tree) by some
details ignored
ie
IF
<exp>
AST
<ifstmt>
<stmt1>
THEN
hV
Parse
Tree
nZ
◦ help subsequence phases not depend on parse process
in
m
Abstract Syntract Tree (AST)
ELSE <stmt2>
<ifstmt>
<exp>
<stmt1>
/>
Dr. Nguyen Hua Phung
Abstract Syntax Tree
<stmt2>
C
o
Expression AST
on
e.
trait Exp
case class BinExp(op:String,e1:Exp,e2:Exp) extends Exp
case class UnaExp(op:String,e:Exp) extends Exp
case class Lit(i:Int) extends Exp
<exp>
nZ
4 * (5 + 3)
<term> *
<fact>
<fact>
(
4
<exp>
ie
<term>
)
+
<term>
hV
<exp>
<term>
<fact>
<fact>
3
in
m
AST for an expression in Scala
5
e1
Lit
i
4
BinExp
e2
* BinExp
e1
e2
Lit
i
5
+
BinExp("*",Lit(4),BinExp("+",Lit(5),Lit(3)))
/>
Dr. Nguyen Hua Phung
Abstract Syntax Tree
Lit
i
3
C
o
e.
Recognizer
on
def fact: Parser[Any] = wholeNumber | "(" ~ exp ~ ")"
ie
nZ
Parser
def fact: Parser[Exp] =
wholeNumber ^^ {case x => Lit(Integer.parseInt(x))}
| "(" ~> exp <~ ")"
hV
12 => Lit(12)
( 120 ) => Lit(120)
in
m
Generate AST in Scala
/>
Dr. Nguyen Hua Phung
Abstract Syntax Tree
C
o
Recognizer
e.
def term: Parser[Any] = fact ~ rep(("*"|"/") ~ fact)
nZ
on
Parser
def term: Parser[Exp]= fact ~ rep(("*"|"/") ~ fact) ^^ {
case a ~ il => il.foldLeft(a)((b,x)=> x match {
case c~d =>BinExp(c,b,d) })
12 * 34 / 6 => Lit(12) ~ [( "*" ~ Lit(34)); ("/" ~ Lit(6))]
("/" ~ Lit(6))
hV
λ
BinExp
ie
λ
Lit(12)
("*" ~ Lit(34))
in
m
Generate AST in Scala (cont’d)
/
BinExp
Lit(6)
*
Lit(12) Lit(34)
BinExp("/",BinExp("*",Lit(12),Lit(34)),Lit(6))
/>
Dr. Nguyen Hua Phung
Abstract Syntax Tree
C
o
e.
on
AST vs. Parse tree
nZ
AST representation in Scala
hV
ie
how to build AST in Scala
in
m
Summary
/>
Dr. Nguyen Hua Phung
Abstract Syntax Tree
