查看正文内容
package mainimport ("bufio""fmt""log""os""strconv""strings"
)type TokenType intconst (tkEOI TokenType = iotatkMultkDivtkModtkAddtkSubtkNegatetkNottkLsstkLeqtkGtrtkGeqtkEqltkNeqtkAssigntkAndtkOrtkIftkElsetkWhiletkPrinttkPutctkLparentkRparentkLbracetkRbracetkSemitkCommatkIdenttkIntegertkString
)type NodeType intconst (ndIdent NodeType = iotandStringndIntegerndSequencendIfndPrtcndPrtsndPrtindWhilendAssignndNegatendNotndMulndDivndModndAddndSubndLssndLeqndGtrndGeqndEqlndNeqndAndndOr
)type tokS struct {
tok TokenTypeerrLn interrCol inttext string // ident or string literal or integer value
}type Tree struct {
nodeType NodeTypeleft *Treeright *Treevalue string
}// dependency: Ordered by tok, must remain in same order as TokenType consts
type atr struct {
text stringenumText stringtok TokenTyperightAssociative boolisBinary boolisUnary boolprecedence intnodeType NodeType
}var atrs = []atr{
{
"EOI", "End_of_input", tkEOI, false, false, false, -1, -1},{
"*", "Op_multiply", tkMul, false, true, false, 13, ndMul},{
"/", "Op_divide", tkDiv, false, true, false, 13, ndDiv},{
"%", "Op_mod", tkMod, false, true, false, 13, ndMod},{
"+", "Op_add", tkAdd, false, true, false, 12, ndAdd},{
"-", "Op_subtract", tkSub, false, true, false, 12, ndSub},{
"-", "Op_negate", tkNegate, false, false, true, 14, ndNegate},{
"!", "Op_not", tkNot, false, false, true, 14, ndNot},{
"<", "Op_less", tkLss, false, true, false, 10, ndLss},{
"<=", "Op_lessequal", tkLeq, false, true, false, 10, ndLeq},{
">", "Op_greater", tkGtr, false, true, false, 10, ndGtr},{
">=", "Op_greaterequal", tkGeq, false, true, false, 10, ndGeq},{
"==", "Op_equal", tkEql, false, true, false, 9, ndEql},{
"!=", "Op_notequal", tkNeq, false, true, false, 9, ndNeq},{
"=", "Op_assign", tkAssign, false, false, false, -1, ndAssign},{
"&&", "Op_and", tkAnd, false, true, false, 5, ndAnd},{
"||", "Op_or", tkOr, false, true, false, 4, ndOr},{
"if", "Keyword_if", tkIf, false, false, false, -1, ndIf},{
"else", "Keyword_else", tkElse, false, false, false, -1, -1},{
"while", "Keyword_while", tkWhile, false, false, false, -1, ndWhile},{
"print", "Keyword_print", tkPrint, false, false, false, -1, -1},{
"putc", "Keyword_putc", tkPutc, false, false, false, -1, -1},{
"(", "LeftParen", tkLparen, false, false, false, -1, -1},{
")", "RightParen", tkRparen, false, false, false, -1, -1},{
"{", "LeftBrace", tkLbrace, false, false, false, -1, -1},{
"}", "RightBrace", tkRbrace, false, false, false, -1, -1},{
";", "Semicolon", tkSemi, false, false, false, -1, -1},{
",", "Comma", tkComma, false, false, false, -1, -1},{
"Ident", "Identifier", tkIdent, false, false, false, -1, ndIdent},{
"Integer literal", "Integer", tkInteger, false, false, false, -1, ndInteger},{
"String literal", "String", tkString, false, false, false, -1, ndString},
}var displayNodes = []string{
"Identifier", "String", "Integer", "Sequence", "If", "Prtc", "Prts", "Prti","While", "Assign", "Negate", "Not", "Multiply", "Divide", "Mod", "Add","Subtract", "Less", "LessEqual", "Greater", "GreaterEqual", "Equal","NotEqual", "And", "Or",
}var (err errortoken tokSscanner *bufio.Scanner
)func reportError(errLine, errCol int, msg string) {
log.Fatalf("(%d, %d) error : %s\n", errLine, errCol, msg)
}func check(err error) {
if err != nil {
log.Fatal(err)}
}func getEum(name string) TokenType {
// return internal version of name#for _, atr := range atrs {
if atr.enumText == name {
return atr.tok}}reportError(0, 0, fmt.Sprintf("Unknown token %s\n", name))return tkEOI
}func getTok() tokS {
tok := tokS{
}if scanner.Scan() {
line := strings.TrimRight(scanner.Text(), " \t")fields := strings.Fields(line)// [ ]*{lineno}[ ]+{colno}[ ]+token[ ]+optionaltok.errLn, err = strconv.Atoi(fields[0])check(err)tok.errCol, err = strconv.Atoi(fields[1])check(err)tok.tok = getEum(fields[2])le := len(fields)if le == 4 {
tok.text = fields[3]} else if le > 4 {
idx := strings.Index(line, `"`)tok.text = line[idx:]}}check(scanner.Err())return tok
}func makeNode(nodeType NodeType, left *Tree, right *Tree) *Tree {
return &Tree{
nodeType, left, right, ""}
}func makeLeaf(nodeType NodeType, value string) *Tree {
return &Tree{
nodeType, nil, nil, value}
}func expect(msg string, s TokenType) {
if token.tok == s {
token = getTok()return}reportError(token.errLn, token.errCol,fmt.Sprintf("%s: Expecting '%s', found '%s'\n", msg, atrs[s].text, atrs[token.tok].text))
}func expr(p int) *Tree {
var x, node *Treeswitch token.tok {
case tkLparen:x = parenExpr()case tkSub, tkAdd:op := token.toktoken = getTok()node = expr(atrs[tkNegate].precedence)if op == tkSub {
x = makeNode(ndNegate, node, nil)} else {
x = node}case tkNot:token = getTok()x = makeNode(ndNot, expr(atrs[tkNot].precedence), nil)case tkIdent:x = makeLeaf(ndIdent, token.text)token = getTok()case tkInteger:x = makeLeaf(ndInteger, token.text)token = getTok()default:reportError(token.errLn, token.errCol,fmt.Sprintf("Expecting a primary, found: %s\n", atrs[token.tok].text))}for atrs[token.tok].isBinary && atrs[token.tok].precedence >= p {
op := token.toktoken = getTok()q := atrs[op].precedenceif !atrs[op].rightAssociative {
q++}node = expr(q)x = makeNode(atrs[op].nodeType, x, node)}return x
}func parenExpr() *Tree {
expect("parenExpr", tkLparen)t := expr(0)expect("parenExpr", tkRparen)return t
}func stmt() *Tree {
var t, v, e, s, s2 *Treeswitch token.tok {
case tkIf:token = getTok()e = parenExpr()s = stmt()s2 = nilif token.tok == tkElse {
token = getTok()s2 = stmt()}t = makeNode(ndIf, e, makeNode(ndIf, s, s2))case tkPutc:token = getTok()e = parenExpr()t = makeNode(ndPrtc, e, nil)expect("Putc", tkSemi)case tkPrint: // print '(' expr {',' expr} ')'token = getTok()for expect("Print", tkLparen); ; expect("Print", tkComma) {
if token.tok == tkString {
e = makeNode(ndPrts, makeLeaf(ndString, token.text), nil)token = getTok()} else {
e = makeNode(ndPrti, expr(0), nil)}t = makeNode(ndSequence, t, e)if token.tok != tkComma {
break}}expect("Print", tkRparen)expect("Print", tkSemi)case tkSemi:token = getTok()case tkIdent:v = makeLeaf(ndIdent, token.text)token = getTok()expect("assign", tkAssign)e = expr(0)t = makeNode(ndAssign, v, e)expect("assign", tkSemi)case tkWhile:token = getTok()e = parenExpr()s = stmt()t = makeNode(ndWhile, e, s)case tkLbrace: // {stmt}for expect("Lbrace", tkLbrace); token.tok != tkRbrace && token.tok != tkEOI; {
t = makeNode(ndSequence, t, stmt())}expect("Lbrace", tkRbrace)case tkEOI:// do nothingdefault:reportError(token.errLn, token.errCol,fmt.Sprintf("expecting start of statement, found '%s'\n", atrs[token.tok].text))}return t
}func parse() *Tree {
var t *Treetoken = getTok()for {
t = makeNode(ndSequence, t, stmt())if t == nil || token.tok == tkEOI {
break}}return t
}func prtAst(t *Tree) {
if t == nil {
fmt.Print(";\n")} else {
fmt.Printf("%-14s ", displayNodes[t.nodeType])if t.nodeType == ndIdent || t.nodeType == ndInteger || t.nodeType == ndString {
fmt.Printf("%s\n", t.value)} else {
fmt.Println()prtAst(t.left)prtAst(t.right)}}
}func main() {
source, err := os.Open("source.txt")check(err)defer source.Close()scanner = bufio.NewScanner(source)prtAst(parse())
}
输出：
Sequence
Sequence
Sequence
Sequence
Sequence
;
Assign
Identifier count
Integer 1
Assign
Identifier n
Integer 1
Assign
Identifier limit
Integer 100
While
Less
Identifier n
Identifier limit
Sequence
Sequence
Sequence
Sequence
Sequence
;
Assign
Identifier k
Integer 3
Assign
Identifier p
Integer 1
Assign
Identifier n
Add
Identifier n
Integer 2
While
And
LessEqual
Multiply
Identifier k
Identifier k
Identifier n
Identifier p
Sequence
Sequence
;
Assign
Identifier p
NotEqual
Multiply
Divide
Identifier n
Identifier k
Identifier k
Identifier n
Assign
Identifier k
Add
Identifier k
Integer 2
If
Identifier p
If
Sequence
Sequence
;
Sequence
Sequence
;
Prti
Identifier n
;
Prts
String " is prime\n"
;
Assign
Identifier count
Add
Identifier count
Integer 1
;
Sequence
Sequence
Sequence
;
Prts
String "Total primes found: "
;
Prti
Identifier count
;
Prts
String "\n"
;