0.前置き
始めたきっかけ
もともと興味があったので、先輩方がtwitter上で話しているのを見た期に始めてみました
対象読者
プログラミング言語を作って見たいけどどこから始めればいいかわからない方
写経していただければ何かがつかめるかも？
注意
僕は初心者です間違った事を言っている可能性があります
鵜呑みにしないでください
また、間違いを見つけたらコメント欄で指摘してくれるとありがたいです
1.仕組み
文字列が与えられたら、それをlexserにかけて単語ごとに分割します
その単語を左から一文字読み込んで文構造を決定する事を繰り返し行います
今回は再帰下降構文解析という手法を用いてLL(1)文法(難しいので自分で調べてほしいですが、要するに左から一文字で文法が決定できるという意味です)を構文解析します。
これは王道的な手法になります(多分)
2.定数の定義
（多分あまり良くないのですが）tokenや非終端記号を#defineを使ってID管理しています
適当なので使ってない定数もあります
#pragma once
#define ep 0
#define EOL 1
#define NUM 2
#define ADD 3
#define SUB 4
#define MUL 5
#define DIV 6
#define LPER 7
#define RPER 8
#define EQ 9
#define STR 10
#define VAR 11
#define SPACE 12
#define ERROR 13
#define START 0
#define term 1
#define factor 2
3.Token
lexerで解析した単語はTokenクラスのqueueにまとめる事にするので、Tokenクラスの定義を行います。Tokenの種別とデータを入れておくだけの簡単なやつです。
例)"1"なら、type=NUM,data="1"
#pragma once
#include<bits/stdc++.h>
using namespace std;
class Token{
public:
int type;
string data;
Token(int type,string data):type(type),data(data){};
string toString(){
return data;
}
};
4.字句解析機/lexer
いよいよコードを単語ごとに分けていきます
正規表現を使って、左端から数文字切ると単語になるようなものをTokenにして切り落としていきます。対応する文字がない場合はtype=ERRORのTokenを渡します
ここからhファイルとcppファイルを分けて行きますTokenも分けろ、ついでにrep文使うな
#pragma once
#include<bits/stdc++.h>
using namespace std;
class Lexer{
public:
queue<Token>que;
smatch match;
vector<regex>v={regex("\\+"),regex("-"),regex("\\*"),regex("/"),regex("\\="),regex("[0-9]+"),regex("\"*\""),regex("[a-z_A-Z][a-z_A-Z0-9]*"),regex(" "),regex(".")};
vector<int>v2={ADD,SUB,MUL,DIV,EQ,NUM,STR,VAR,SPACE,ERROR};
Lexer(string str,int line);
};
#include<bits/stdc++.h>
#include"./const.h"
#include"./token.h"
#include"./lexer.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define repi(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(),v.end()
using namespace std;
Lexer::Lexer(string str,int line){
int start=0;
string s;
while(start<str.size()){
for(int i=0;i<v.size();i++){
regex r=v[i];
s=str.substr(start);
if(regex_search(s,match,r)&&match.position()==0){
que.push(Token(v2[i],match.str()));
start+=match.length();
break;
}
}
}
que.push(Token(EOF,"\n"));
}
5.構文解析機/parser
今回の目玉です
拡張BNF記法(文法を定義する物)でいうところの
<START> ::= <term> [ ('+'|'-') <term> ]*
<term> ::= <factor> [ ('*'|'/') <factor> ]*
<factor> ::= '(' <START> ')' | <NUM>
を実装していきます。
拡張性に乏しいので改善案を考えています
構文解析 - アルゴリズム講習会
を参考に実装したのでわからなくなったらこっちを見るのもいいかもしれません
#pragma once
#include<bits/stdc++.h>
#include"./Lexer.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define repi(i,a,b) for(int i=a;i<b;i++)
using namespace std;
struct Parser{
public:
Parser();
int parse(queue<Token>&,int expr);
};
#include<bits/stdc++.h>
#include"./const.h"
#include"./token.h"
#include"./parser.h"
#define rep(i,n) for(int i=0;i<n;i++)
#define repi(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(),v.end()
using namespace std;
Parser::Parser(){}
int Parser::parse(queue<Token>& line,int expr){
int val;
switch(expr){
case START:{
val=parse(line,term);
while(line.front().type==ADD||line.front().type==SUB){
int op=line.front().type;
line.pop();
int val2=parse(line,term);
if(op==ADD)val+=val2;
else val-=val2;
break;
}
break;
}
case term:{
val=parse(line,factor);
while(line.front().type==MUL||line.front().type==DIV){
int op=line.front().type;
line.pop();
int val2=parse(line,factor);
if(op==MUL)val*=val2;
else val/=val2;
break;
}
break;
}
case factor:{
if(line.front().type==NUM){
val=stoi(line.front().toString());
line.pop();
return val;
}
line.pop();
val =parse(line,START);
line.pop();
break;
}
}
return val;
}
6.実行
たったこれだけ！
#include<bits/stdc++.h>
#include"./const.h"
#include"./token.h"
#include"./lexer.h"
#include"./parser.h"
using namespace std;
int main(){
string eval="1+2*(3+1)";
Lexer lex=Lexer(eval,0);
Parser parser=Parser();
int i=0;
cout<<eval<<"="<<parser.parse(lex.que,START);
}
7.作ってみた感想
文法ごとに関数を書いていく手法さえとればparserもそこまで難しくない印象でしたが、今後の拡張の為に文法の拡張手法を整備するのが今後の課題です
慣れれば本格的なインタプリタも書けるのでは！？と思いました