世に parser generator や parser combinator が生まれてから兔角、文脈自由或いはそれに近い文法の構文解析器を作るのは簡單で、私も度々作ってきた。
PEG (Parsing Expression Grammar) が表現し易く好きでよく使ってゐた。PEG.js – Parser Generator for JavaScript で書いたものは或る程度大きな Web site で暫く動いてゐた。今は置き換へられたやうだ。或いは擴張を加えられただけかもしれないが判らない。hafriedlander/php-peg: PEG (parsing expression grammar) compiler for PHP では PHP の doc comment に annotation を書いて (doc comment に annotation を書く手法は PHP で度々使はれる) DI/AOP を行ふべく、doc string と annotation 内の DSL (Domain-Specific Language) の構文解析器を書いた。
單純な文法であれば yacc 系の LALR (LookAhead Left-to-Right) parser でも使ひ勝手は同じだ。Erlang/OTP には lexx と yecc と云ふ lexer generator と parser generator とが組み込まれてゐ、これを使って DSL を書いた。
今囘 PEG.js で昔書いた DSL を Python (Transcrypt) で書直す事にした。新たに PEG.js で書き起こしたり、Python の PEG library を使ふ事も出來たが、language agnostic な手法を手に入れたかったから ANTLR4 を使ってみる事にした。初めて LL (Left-to-Left) parser を使ふがなんとか成るであらう。果たしてなんとか成った。
作る DSL の仕樣を非形式的に書くと、
root := 規則定義 規則定義 …
規則定義 :=
規則名 '=' 規則 ;
規則名 := [A-Z][0-9A-Za-z]*
規則 := 選擇規則 | 規則の差 | 單純規則 | 列規則
選擇規則 := 列規則 正の整數 '|' 列規則 正の整數 '|' …
規則の差 := ( '{' 選擇規則 '}' | 規則名 ) '-' ( 文字列 | 規則名 | 參照規則 )
單純規則 := '{' 規則 '}' | 規則名 | 文字列 | 參照規則
列規則 := 單純規則 單純規則 …
正の整數 := 所謂正の整數
文字列 := '"' 所謂文字列 '"'
參照規則 := ref '{' 規則名 正の整數 '}'
これを左再歸に注意し乍ら (上記の仕樣は下記の g4 から書き起こしたものなので、既に左再歸を取り除いてある) ANTLR4 の DSL である g4 で書くとこう成る。
grammar DekuRule;
root
: wordDefinition *
;
choiceWord
: (sequenceWord PositiveInteger OrOperator) + sequenceWord PositiveInteger
;
differenceLhs
: OpenParenthesis choiceWord CloseParenthesis
| WordName
;
differenceRhs
: String
| WordName
| referenceWord
;
differenceWord
: differenceLhs DifferenceOperator differenceRhs
;
elementWord
: OpenParenthesis word CloseParenthesis
| WordName
| String
| referenceWord
;
referenceWord
: ReferenceCall OpenArguments WordName PositiveInteger CloseArguments
;
sequenceWord
: elementWord +
;
word
: choiceWord
| differenceWord
| elementWord
| sequenceWord
;
wordDefinition
: WordName DefineOperator word DefinitionTerminator
;
CloseArguments : ')' ;
CloseParenthesis : '}' ;
DefineOperator : '=' ;
DefinitionTerminator : ';' ;
DifferenceOperator : '-' ;
OpenArguments : '(' ;
OpenParenthesis : '{' ;
OrOperator : '|' ;
PositiveInteger : ('0' | [1-9][0-9]*) ;
ReferenceCall : 'ref' ;
String : '"' ('\\"'|~'"')* '"' ;
WhiteSpace : [ \t\r\n]+ -> skip ;
WordName : [A-Z][0-9A-Za-z]* ;
PEG と yacc の間の子の氣分だ。
さてこれを Transcrypt で動かすには、先ず g4 を JavaScript に吐き出しそれを Python から呼び出す。g4 を Python に吐き出したものには Transcrypt が對應しない函數が使はれてゐるからだ。
ANTRL4 は Java で作られてゐるから JRE を、Alpine Linux であればopenjdk11-jreを入れる。適當な所にantlr-4.x-complete.jarを下載して、置く。4.xは最新の ver.に置き換へる事。g4 をsifaru_yusin/DekuRule.g4と云ふ file に書くとすると、
cd sifaru_yusin && java -cp "/path/to/antlr-4.x-complete.jar:$CLASSPATH" org.antlr.v4.Tool -Dlanguage=JavaScript DekuRule.g4
で、JavaScript で動く lexer と parser とを生成出來る。JavaScript を讀み込むにはPython で React Web front を書く - c4se 記：さっちゃんですよ ☆で紹介した手法を使ふ。antlr4を node_modules に追加して、
import typing as t __pragma__( # noqa: F821 "js", "{}", """ const antlr4 = require("antlr4"); const { DekuRuleLexer } = require("../sifaru_yusin/DekuRuleLexer"); const { DekuRuleListener } = require("../sifaru_yusin/DekuRuleListener"); const { DekuRuleParser } = require("../sifaru_yusin/DekuRuleParser"); """, ) antlr4: t.Any = 0 # __:skip DekuRuleLexer: t.Any = 0 # __:skip DekuRuleListener: t.Any = 0 # __:skip DekuRuleParser: t.Any = 0 # __:skip
とすれば ANTLR4 が生成した class を呼べるやうに成る。
chars = __new__(antlr4.InputStream(source)) # noqa: F821 lexer = __new__(DekuRuleLexer(chars)) # noqa: F821 tokens = __new__(antlr4.CommonTokenStream(lexer)) # noqa: F821 parser = __new__(DekuRuleParser(tokens)) # noqa: F821 parser.buildParseTrees = True tree = oparser.root()
これで構文木が得られる。この當りもこの先も、ANTLR4 の document に全て書いてあるのでそちらを讀む事。
- antlr4/lexer-rules.md at master · antlr/antlr4
- antlr4/parser-rules.md at master · antlr/antlr4
- antlr4/javascript-target.md at master · antlr/antlr4
得られた構文木を辿ったり變換したりしたい。辿るには listener が、變換するには visitor が用意されてゐる。listener は lexer や parser と共に生成されてゐる。これを繼承すれば好いが、Transcrypt から JavaScript の class を繼承は出來ないから、翻譯する class を作る。
class DekuRuleListener_py: """ANTLR4 tree listener.""" def __init__(self): """Initialize a listener.""" self.original = __new__(DekuRuleListener()) # noqa: F821 def visitTerminal(self, node): """Handle a callback when the listener traverse a terminal node.""" return self.original.visitTerminal(node) def visitErrorNode(self, node): """Handle a callback when the listener traverse an error node.""" return self.original.visitErrorNode(node) def enterEveryRule(self, node): """Handle a callback when the listener enter a non terminal rule.""" return self.original.enterEveryRule(node) def exitEveryRule(self, node): """Handle a callback when the listener exit from a non terminal rule.""" return self.original.exitEveryRule(node) class DekuRulePrinter(DekuRuleListener_py): """ANTLR4 custom tree listener.""" # …
かうしておいて、
antlr4.tree.ParseTreeWalker.DEFAULT.walk(DekuRulePrinter(), tree)
とすると構文木を深さ優先で辿って各 node 毎に method を呼んでくれる。後は好きにする。visitor は生成も出來るが標準では生成されないし、どうせ繼承出來ないから要らないだらう。自分で作るのが簡單だ。visitChildrenとvisitTerminalが ANTLR4 の期待する interface である。例へば、
class Visitor: """ANTLR4 custom tree visitor.""" def visitChildren(self, context): """Handle a callback when the visitor visit a non terminal node.""" rule_name = context.parser.ruleNames[context.ruleIndex] if rule_name == "root": return self.__visit_root(context) elif rule_name == "choiceWord": return self.__visit_choiceWord(context) elif rule_name == "differenceLhs": return self.__visit_differenceLhs(context) elif rule_name == "differenceRhs": return self.__visit_differenceRhs(context) elif rule_name == "differenceWord": return self.__visit_differenceWord(context) elif rule_name == "elementWord": return self.__visit_elementWord(context) elif rule_name == "referenceWord": return self.__visit_referenceWord(context) elif rule_name == "sequenceWord": return self.__visit_sequenceWord(context) elif rule_name == "word": return self.__visit_word(context) elif rule_name == "wordDefinition": return self.__visit_wordDefinition(context) else: raise Exception("Unknown rule: {}".format(rule_name)) def visitTerminal(self, context): """Handle a callback when the visitor visit a terminal node.""" symbolic_name = context.parentCtx.parser.symbolicNames[context.symbol["type"]] if symbolic_name == "CloseArguments": return None elif symbolic_name == "CloseParenthesis": return ("CloseParenthesis",) elif symbolic_name == "DefineOperator": return None elif symbolic_name == "DefinitionTerminator": return None elif symbolic_name == "DifferenceOperator": return None elif symbolic_name == "OpenArguments": return None elif symbolic_name == "OpenParenthesis": return ("OpenParenthesis",) elif symbolic_name == "OrOperator": return None elif symbolic_name == "PositiveInteger": return ("PositiveInteger", int(context.getText())) elif symbolic_name == "ReferenceCall": return None elif symbolic_name == "String": return StringRule(eval(context.getText())) elif symbolic_name == "WhiteSpace": raise Exception("WhiteSpace must skip by the parser.") elif symbolic_name == "WordName": return ("WordName", context.getText()) else: raise Exception("Unknown symbol: {}".format(symbolic_name)) # …
各 node では、
children = [child.accept(self) for child in context.children]
を呼べば深さ優先で辿れる。
これで變換出來る。
rule_definitions = tree.accept(Visitor())
型檢査も實裝すると便利だらうが構文が充分に制約されてゐるのでそれはサボった。
以下で實例が動いてゐる。
