この記事の続きです。
軸解析と構文解析を一緒の記事すると長くなりそうなので分けました。
リポジトリ
構文解析器(parser)とは
軸解析の結果から木構造を生成してインタプリタに渡すものです。
例えば下記のトークンの定義とトークン列がありパースを行うと。
const a = 1
-
constは変数定義のキーワードで1と定義する -
aは変数名でキーワード以外は2と定義する -
=は演算子で3と定義する -
1は数列で4と定義する
[1, 2, 3, 4]
{value:1, node: { value: '3', node: { value: 4 }}}
上記のような感じになります。
木構造の生成は仕様により異なり、どれが正解とかはないです。
{value: '3',node: [{ value: 2 }, { value: 4 }]}
例えば演算子の左辺と右辺で構造化するような物もあります。
実装する際の考え方
定義とパースする構文は上記のものを同じです。
[1, 2, 3, 4]
上記のトークンの配列を前から順番に見ていき木構造に落とし込んでいきます。
[1, 2, 3, 4]
↑
まず最初に1が渡されるので次のトークンの2が変数であり、変数定義の処理に入ることがわかります
[1, 2, 3, 4]
↑
{ value: 2, node: null }
変数を定義する処理なのでキーワードである1の次は2の変数名でなければならないです。
2が渡されているので変数名と変数のノードが作成されます。
[1, 2, 3, 4]
↑
{ value: 2, node: { value: 3, node: null } }
変数を定義する処理なので1, 2とくれば次は絶対に3でなければならないです。
3であった場合、変数のノードに演算子のノードが中に入ります。
[1, 2, 3, 4]
↑
{ value: 2, node: { value: 3, node: { value: 4 } } }
最後に4が来ているので演算子のノードに4が入ります。
これで構文解析が完了します。
実装(一部抜粋)
#[derive(Debug, Clone)]
pub enum Types {
...
Variable(VariableAST),
...
}
#[derive(Debug, Clone)]
pub enum VariableTypes {
Bool,
Int,
Strings,
Binary,
Void,
}
#[derive(Debug)]
pub struct ExprAST {
pub node: Vec<Types>,
}
impl ExprAST {
pub fn new() -> ExprAST {
ExprAST { node: Vec::new() }
}
}
#[derive(Debug, Clone)]
pub struct VariableAST{
pub name: String,
pub index:Option<Vec<Types>>,
pub muttable: bool,
pub types: Option <VariableTypes>,
pub node: Vec<Types>,
}
Rustの場合、型の制約があるのでenumを使い、さらに構文解析上の型を定義して構造体に全てのnodeを持たせられるようにしています。
変数のノードには各種設定も定義してあります(あんまりよくない気もする)。
if token == token_constant._let || token == token_constant._const {
self.tokens.remove(0);
let string = &self.tokens[0].val;
let mut variable = asts::VariableAST::new(string);
if token == token_constant._const {
variable.mutable = false;
}
let variable = asts::Types::Variable(variable);
if self.tokens[1].token != 61 {
let error = error::Error::new(&self.tokens[0]);
error.exit("opcode error is not =");
}
self.tokens.remove(0);
self.tokens.remove(0);
return variable;
}
変数を定義する際の処理の抜粋です。
if token == token_constant._let || token == token_constant._const {
...
letもしくはconstに定義してあるトークンの場合この処理に入ります。
self.tokens.remove(0);
let string = &self.tokens[0].val;
let mut variable = asts::VariableAST::new(string);
配列をremove()で進めてトークンと一緒に入ってる中身の文字列を取り出しています。
文字列を使い新しいVariableのノードを作成しています。
self.tokens.remove(0);
self.tokens.remove(0);
return variable;
最後にトークンを進めて、作ったノードを返しています。
返したノードをルートのノードに入れれば処理の完了です。
Discussion