詞法分析-Antlr-1

在上一節(jié)中我們提到了,我們可以根據(jù)一種叫 有限自動(dòng)機(jī) 的東西將字符串分割成多個(gè)Token。

下面是一段swift代碼,其中實(shí)現(xiàn)了一些基礎(chǔ)Token的解析,原理就是: 有限自動(dòng)機(jī)

//
//  ScriptLexer.swift
//  MyScriptCompiler
//
//  Created by legendry on 2019/8/21.
//  Copyright ? 2019 legendry. All rights reserved.
//
import Foundation
/// 腳本語(yǔ)言詞法分析器
public class ScriptLexer {
    
    public enum ScriptLexer: Error {
        /// 源碼為空
        case SourceCodeEmpty
        /// 語(yǔ)法錯(cuò)誤
        case SyntaxError(reason: String)
    }
    /// 詞法分析器的有限狀態(tài)機(jī)狀態(tài)
    var fsmType = FSMType.Initial
    /// 默認(rèn)token為nil
    var token: ScriptToken? = nil
    var _tmpTokens = [ScriptToken]()
    /// 初始化新的token
    /// 將狀態(tài)機(jī)遷移到新的狀態(tài)
    private func initToken(_ c: UInt8) throws -> FSMType {
        var _fsmType = FSMType.Unknow
        if let _t = token {
            /// 將解析到的token保存起來(lái)
            _tmpTokens.append(_t)
            token = nil
        }
        if c.isLetter {
            /// 當(dāng)我們解析到字符i時(shí),當(dāng)前認(rèn)為他是一個(gè)標(biāo)識(shí)符
            token = ScriptToken(type: .Identifier)
            token?.appendTokenText(c: c)
            if c.char == "i" {
                /// 狀態(tài)機(jī)狀態(tài)切換至標(biāo)識(shí)符i,如果后續(xù)是nt并以空格結(jié)束,則解析成int
                /// 否則解析成標(biāo)識(shí)符
                _fsmType = .Identifier_Int_i
            } else {
                _fsmType = .Identifier
            }
        } else if c.char == "=" {
            token = ScriptToken(type: .EQ)
            token?.appendTokenText(c: c)
            _fsmType = .EQ
        } else if c.isDigit {
            token = ScriptToken(type: .IntLiteral)
            token?.appendTokenText(c: c)
            _fsmType = .IntLiteral
        } else if c.char == ">" {
            token = ScriptToken(type: .GT)
            token?.appendTokenText(c: c)
            _fsmType = .GT
        } else if c.char == "<" {
            token = ScriptToken(type: .LT)
            token?.appendTokenText(c: c)
            _fsmType = .LT
        } else if c.char == "-" {
            token = ScriptToken(type: .Minus)
            token?.appendTokenText(c: c)
            _fsmType = .Minus
        } else if c.char == "*" {
            token = ScriptToken(type: .Star)
            token?.appendTokenText(c: c)
            _fsmType = .Star
        } else if c.char == "+" {
            token = ScriptToken(type: .Plus)
            token?.appendTokenText(c: c)
            _fsmType = .Plus
        } else if c.char == "/" {
            token = ScriptToken(type: .Slash)
            token?.appendTokenText(c: c)
            _fsmType = .Slash
        } else if c.char == "(" {
            token = ScriptToken(type: .LeftBracket)
            token?.appendTokenText(c: c)
            _fsmType = .LeftBracket
        } else if c.char == ")" {
            token = ScriptToken(type: .RightBracket)
            token?.appendTokenText(c: c)
            _fsmType = .RightBracket
        } else {
            if c.isValid {
                _fsmType = .Initial
            } else {
                throw ScriptLexer.SyntaxError(reason: "不支持: \\(c.char)")
            }
        }
        return _fsmType
        
    }
    
    
    /// 解析腳本,生成Token
    /// 利用有限狀態(tài)自動(dòng)機(jī)在不同狀態(tài)之間遷移得到不同的Token
    /// int age = 45
    /// age >= 3
    public func analysis(script: String) throws -> ScriptTokenReader {
        _tmpTokens.removeAll()
        fsmType = FSMType.Initial
        token = nil
        
        guard script.count > 0 else {
            throw ScriptLexer.SourceCodeEmpty
        }
        let charReader = CharReader(script)
        /// 開(kāi)始分析源碼
        while let c = charReader.read() {
            switch fsmType {
            case .Initial:
                self.fsmType = try initToken(c)
            case .Identifier_Int_i:
                /// 第一個(gè)字母是i,如果第二個(gè)字母是n則狀態(tài)機(jī)遷移至Identifier_Int_n
                /// 否則狀態(tài)機(jī)遷移至Identifier
                if c.char == "n" {
                    self.fsmType = .Identifier_Int_n
                    token?.appendTokenText(c: c)
                } else if c.isTail {
                    /// 當(dāng)前token標(biāo)識(shí)完成
                    /// 狀態(tài)機(jī)重置
                    self.fsmType = try initToken(c)
                } else {
                    /// 狀態(tài)機(jī)遷移至標(biāo)識(shí)符狀態(tài),繼續(xù)解析標(biāo)識(shí)符token
                    self.fsmType = .Identifier
                    token?.appendTokenText(c: c)
                }
            case .Identifier_Int_n:
                if c.char == "t" {
                    self.fsmType = .IntLiteral
                    token?.appendTokenText(c: c)
                    /// 這里暫時(shí)將類型切換成Int,如果后面還有字符則表式是一個(gè)標(biāo)識(shí)符,再切換類型
                    token?.type = .Int
                } else if c.isTail {
                    /// 當(dāng)前token標(biāo)識(shí)完成
                    /// 狀態(tài)機(jī)重置
                    self.fsmType = try initToken(c)
                } else {
                    /// 狀態(tài)機(jī)遷移至標(biāo)識(shí)符狀態(tài),繼續(xù)解析標(biāo)識(shí)符token
                    self.fsmType = .Identifier
                    token?.appendTokenText(c: c)
                }
            case .IntLiteral:
                if c.isTail {
                    /// 當(dāng)前token標(biāo)識(shí)完成
                    /// 狀態(tài)機(jī)重置
                    self.fsmType = try initToken(c)
                } else if c.char == "+" || c.char == "-" || c.char == "*" || c.char == "/" /*|| c.char == "(" || c.char == ")"*/ {
                    self.fsmType = try initToken(c)
                } else if c.isLetter {
                    throw ScriptLexer.SyntaxError(reason: "非數(shù)字字面量")
                } else {
                    token?.appendTokenText(c: c)
                }
            case .Identifier:
                if c.isTail {
                    self.fsmType = try initToken(c)
                } else {
                    token?.appendTokenText(c: c)
                }
            case .EQ:
                if c.isTail {
                    token?.type = .Assignment
                    self.fsmType = try initToken(c)
                } else {
                    throw ScriptLexer.SyntaxError(reason: "語(yǔ)法異常")
                }
            case .GE, .LE:
                if c.isTail {
                    self.fsmType = try initToken(c)
                } else {
                    throw ScriptLexer.SyntaxError(reason: "語(yǔ)法異常")
                }
            case .LeftBracket, .RightBracket:
                self.fsmType = try initToken(c)
            case .GT:
                if c.isTail {
                    self.fsmType = try initToken(c)
                } else if c.char == "=" {
                    self.fsmType = .GE
                    token?.type = .GE
                    token?.appendTokenText(c: c)
                } else {
                    throw ScriptLexer.SyntaxError(reason: "語(yǔ)法異常")
                }
            case .LT:
                if c.isTail {
                    self.fsmType = try initToken(c)
                } else if c.char == "=" {
                    self.fsmType = .LE
                    token?.type = .LE
                    token?.appendTokenText(c: c)
                } else {
                    throw ScriptLexer.SyntaxError(reason: "語(yǔ)法異常")
                }
            case .Minus, .Plus, .Star, .Slash:
                if c.isTail || c.isDigit {
                    self.fsmType = try initToken(c)
                } else {
                    throw ScriptLexer.SyntaxError(reason: "語(yǔ)法異常")
                }
            default: break
            }
        }
        if let _t = token {
            /// 將解析到的token保存起來(lái)
            _tmpTokens.append(_t)
            token = nil
        }
        let tokenReader = ScriptTokenReader.init(_tmpTokens)
        return tokenReader
    }
}

如果要快速落地一個(gè)DSL原型Demo,全部都自己去寫(xiě)似乎有點(diǎn)慢。所以我們需要借助于工具來(lái)幫我們解析Token, 這個(gè)工具叫做: Antlr https://www.antlr.org/

這個(gè)工具支持很多語(yǔ)言,C++,Swift,Java....,常用的編碼語(yǔ)言都可以。你可以選擇一個(gè)合適你的語(yǔ)言來(lái)實(shí)現(xiàn)DSL了。

下載并配置好Antlr,Antlr本身是Java實(shí)現(xiàn)的，所以你的環(huán)境要運(yùn)行Antlr需要有Java運(yùn)行時(shí)環(huán)境。

配置好Antlr之后,我們就可以借助Antlr來(lái)實(shí)現(xiàn)我們的詞法分析了。Antlr通過(guò)解析規(guī)則文件來(lái)分析我們要分割的Token的規(guī)則,規(guī)則則是用正則表達(dá)式來(lái)書(shū)寫(xiě)。

lexer grammar FlexDSLLexer;
//關(guān)鍵字
If: 'if';
FOR: 'for';
WHILE: 'while';
IN: 'in';
/// 基礎(chǔ)數(shù)據(jù)類型
Int: 'int';
Double: 'double';
Float: 'float';
True: 'true';
False: 'false';
//字面量
IntLiteral: [0-9]+;
DoubleLiteral: [0-9] . [0-9]*;
StringLiteral: '"' .*? '"'; //字符串字面量
//操作符
AssignmentOP: '=';
RelationalOP: '>' | '>=' | '<' | '<=';
Star: '*';
Plus: '+';
Sharp: '#';
SemiColon: ';';
Dot: '.';
Comm: ',';
LeftBracket: '[';
RightBracket: ']';
LeftBrace: '{';
RightBrace: '}';
LeftParen: '(';
RightParen: ')';
//標(biāo)識(shí)符
Id: [a-zA-Z_] ([a-zA-Z_] | [0-9])*;
//空白字符，拋棄
Whitespace: [ \\t]+ -> skip;
Newline: ( '\\r' '\\n'? | '\\n') -> skip;

以上的規(guī)則文件內(nèi)容指定了我們要從字符串中解析出來(lái)的Token,每一個(gè)Token都有一個(gè)名字,后面對(duì)應(yīng)的則是這個(gè)Token的規(guī)則。把這個(gè)文件保存到FlexDSLLexer.g4

然后通過(guò)命令來(lái)編譯

antlr4 FlexDSLLexer.g4

編譯完成得到如下文件

然后使用

javac *.java

編譯完成之后,通過(guò)運(yùn)行g(shù)run命令來(lái)解析并輸出對(duì)應(yīng)的Token(s)

grun FlexDSLLexer tokens -tokens Hello.play

其中Hello.play內(nèi)容如下

int name = "人\\n字";
true
false

最后得到如下輸出,不僅成功的解析出來(lái)了我們指定的Token,還把對(duì)應(yīng)的行列都輸出了。這樣當(dāng)我們?cè)诮馕龀鲥e(cuò)時(shí)也可以報(bào)具體的錯(cuò)誤信息了。到此,我們的詞法解析就完成了,接下來(lái)我們將進(jìn)行語(yǔ)法分析。