はじめに
その辺の学生です。
Processingで自由課題を作る機会があり、折角だし自分の持つ技術力全部使って奇を衒ったもの作りたいなーーーと考えた結果...
Processingを作りました。
技術なんて無駄遣いしてる時が一番楽しいですからね。
その時の制作の流れとかどういう実装したかとかを雑多にまとめた記事になります。
目次
1. エディタ編
プログラム書くための土台が無いと何も始まらないのでProcessing自体のエディタを参考に作っていきたい。
1.1 方針
入力された文字列は全部文字列で管理するだけ。改行とかはエンターキーが押されると¥nを特殊な文字列として追加して、それを認識することで改行判定を行ってみる。
改行によって文字列の分割ーーなんてしてると後々面倒になりそう読みで(実際はそんなことなかった)安直にスクリプトを全部一つの文字列として一元管理したかった。
エディタの文字入力はkeyTyped関数でキーボードの文字認識して文字列に追加する形で。
ここまでは簡単、問題はカーソルとエディタ画面自体。
エディタの画面を動的にしたい
コーディングしてると何百行って書くときもあるでしょう。その中で画面が動かなかったら途中から文字が見えなくなるのは良く無いかも。
カーソルで画面を動かせるよくあるエディタの実装が欲しい。
clipで範囲指定、その中でのみ文字列が表示されるようにして、文字列をマウスのホイールで上下できるようにしてみる。clip便利。
カーソル問題
エディタは文字の位置がほいほい変わるせいでエディタのカーソルをどう合わせるかでちょっと悩んだ。
本題じゃないのでここは妥協して左右キーでのみカーソルを移動できるようにして文字列の何番目にカーソルがあるかで実装する。
1.2 実装してみる
マウスホイールでエディタの画面の位置の座標を調整
void mouseWheel(MouseEvent event){
float e = event.getCount();
scrollcounter += e*20;
if(scrollcounter<=0){
scrollcounter = 0;
}else if(scrollcounter >= lines.length*20 ){
scrollcounter = lines.length*20;
}
}
カーソル位置の計算、描画諸々の実装部分。
元々は左右以外にもマウスとか上下キーでもカーソル移動できるようにしようとしてたため不自然なコードかも。
出自が謎な変数は雰囲気で読み取ってくださいな。
clip(45,150,width*0.9,height*0.6);
fill(0);
textAlign(LEFT,TOP);
textSize(20);
lines = code.split("\n");
pushMatrix();
translate(0, -scrollcounter);
for(int i=0;i<lines.length; i++){
text(i+1,50,160 + i*20);
text(lines[i],80,160 + i*20);
}
//define cursor position
int cursorline = 0;
int cursorcharcount = 0;
for(int i=0;i<lines.length;i++){
int linelength = lines[i].length()+1;
if(cursorposition <= cursorcharcount+linelength){
cursorline = i;
break;
}
cursorcharcount += linelength;
}
//calculate cursor x
String cursorcurrentline = lines[cursorline];
int cursorcolumn = cursorposition - cursorcharcount;
if(cursorcolumn > cursorcurrentline.length()){
cursorcolumn = cursorcurrentline.length();
}
String beforecursor = cursorcurrentline.substring(0,cursorcolumn);
float cursoroffset = textWidth(beforecursor);
cursortimer = (cursortimer+1)%60;
if(cursortimer < 30){
stroke(0);
line(80+cursoroffset, 160+cursorline*20-scrollcounter, 80+cursoroffset, 160+cursorline*20+20-scrollcounter);
}
popMatrix();
noClip();
2. 字句解析編
書いたコードを構文規則などから参照して、意味のある単語として最小単位で区切っていきたい。
字句解析前: int i = 0;
字句解析後: [[int],[i],[=],[0],[;]]
元々あるスクリプトをこのように分割していきます。
現地点ではなんでこんなことすんねんって感じですが後々役立ちます。
2.1 方針
今回は配列ではなくリストで管理していきます。単語の種類に応じてIDを設定して、構文分析で楽する用。
実装は文法に合わせて大体で分類しながら分けていく。
例えば、前から認識していく上で、"の文字を認識した場合、次に"が来るまでは文字列が来ることを期待するみたいな感じ。変数の型の名前とかもifで全部逐一確かめていく。
文字列を分割しまくるだけなので脳死で実装できそう？
2.2 実装してみる
だいぶ力技なのでもうちょっと綺麗にできそう...
ArrayList<Token> tokenize(String code){
ArrayList<Token> tokens = new ArrayList<Token>();
int tokenposition = 0;
int length = code.length();
while(tokenposition < length){
char currentchar = code.charAt(tokenposition);
if(Character.isWhitespace(currentchar)){
tokenposition++;
continue;
}
if(Character.isDigit(currentchar)){
String numstr = "";
while(tokenposition < length && Character.isDigit(code.charAt(tokenposition))){
numstr += code.charAt(tokenposition);
tokenposition++;
}
tokens.add(new Token("NUMBER", numstr));
continue;
}
if(Character.isLetter(currentchar) || currentchar =='_'){
String idstr = "";
while(tokenposition < length && code.charAt(tokenposition) != ' ' && (Character.isLetter(code.charAt(tokenposition)) || code.charAt(tokenposition) == '_')){
idstr += code.charAt(tokenposition);
tokenposition++;
}
if(idstr.equals("int") ||idstr.equals("String")||idstr.equals("float") ||idstr.equals("boolean") ||idstr.equals("var")){
tokens.add(new Token("TYPE", idstr));
}else if(idstr.equals("void") ||idstr.equals("if") ||idstr.equals("for") ||idstr.equals("while")|| idstr.equals("else")){
tokens.add(new Token("KEYWORD",idstr));
}else{
tokens.add(new Token("IDENTIFIER", idstr));
}
continue;
}
if(currentchar == '+'){
tokens.add(new Token("PLUS","+"));
tokenposition++;
continue;
}else if(currentchar == '-'){
//以下略...
}else if(currentchar == '='){
if(tokenposition+1 < length && code.charAt(tokenposition+1)=='='){
tokens.add(new Token("EQ","=="));
tokenposition += 2;
}else{
tokens.add(new Token("EQUALS","="));
tokenposition++;
}
continue;
}else if(currentchar == '!'){
if(tokenposition+1 < length && code.charAt(tokenposition+1)=='='){
tokens.add(new Token("NEQ","!="));
tokenposition += 2;
}else{
tokens.add(new Token("NOT","!"));
tokenposition++;
}
continue;
}else if(currentchar == '<'){
if(tokenposition+1 < length && code.charAt(tokenposition+1)=='='){
tokens.add(new Token("LE","<="));
tokenposition += 2;
}else{
tokens.add(new Token("LT","<"));
tokenposition++;
}
continue;
}else if(currentchar == '>'){
if(tokenposition+1 < length && code.charAt(tokenposition+1)=='='){
tokens.add(new Token("GE",">="));
tokenposition += 2;
}else{
tokens.add(new Token("GT",">"));
tokenposition++;
}
continue;
}else if(currentchar == '&'){
if(tokenposition+1 < length && code.charAt(tokenposition+1)=='&'){
tokens.add(new Token("AND","&&"));
tokenposition += 2;
}else{
tokens.add(new Token("undefinedtoken","&"));
tokenposition++;
}
continue;
}else if(currentchar == '|'){
if(tokenposition+1 < length && code.charAt(tokenposition+1)=='|'){
tokens.add(new Token("OR","||"));
tokenposition += 2;
}else{
tokens.add(new Token("undefinedtoken","|"));
tokenposition++;
}
continue;
}else if(currentchar == '"'){
tokenposition++;
String strstr = "";
while(tokenposition < length && code.charAt(tokenposition) != '"'){
strstr += code.charAt(tokenposition);
tokenposition++;
}
tokenposition++;
tokens.add(new Token("STRING", strstr));
continue;
}else{
println("undefined string: " + currentchar);
tokenposition++;
continue;
}
}
return tokens;
}
if,else if,else if...以下略
何とかしたかったけど改善案全く思いつかなかった、、、
3. 構文分析編
プログラムの構造を実行できるように整理したい。そんな時に使われるのが構文分析及び構文木。
構文木はプログラムの構造を木構造にしたもの。
processingで言うと、void draw()関数があって、その中に描画関数があったり変数の宣言があったりwhile(条件式){中身の処理}といったような形で更に深い部分に処理があったりする感じ。
自分はインデントの機械版みたいに解釈してます。
3.1 方針
さあ構文木を作るぜ！といったところで何も下調べせずにかけるものではないので色々調べてみる。
構文木にも色々あるみたいですが、今回は抽象構文木を再現していきます。
プログラムの中身を再帰的に認識していくことで木構造を作ることはできそう。これはどう動かすかを完全に決め切ってから作るべきかも？
3.2 構文木と文法規則
構文分析のための構文木を作るために構文気をどう作るかを具体的に決めていきたい。
そこで、processingの文法規則を持ち出します。
文法規則といっても、rectで四角形を描画できるよーみたいな話とはちょっと違って、もっと抽象度を上げた構造、rectなら引数が必要な関数としてのみ扱います。
更に根本の、プログラム全体を管理するためにvoid draw()関数内であればそれ全体を幾らかの関数や変数宣言、演算といった処理の集合体と捉え、その中にまた処理の集合体があり、具体的に引数を取ってそれ以上取るものが無いところまで探索できるように文法規則を自分で再定義したいと言うのがこれを行う目的です。実装の時に何を呼び出せば良いかがわかりやすくなるので必須だった。
文法規則を定めてみる
文法規則を定める上で、BNF記法というものを扱います。
<function> ::= <identifier> "(" <argument> ")"
上記のような記法でこの機能はこのような値を取るよーというのを明示する感じ。それを基にして構文分析を行うプログラムを書いていきたい。
そして、実際に使う文法規則が以下の通り
<program> ::= { <function_declaration> }
<function_declaration> ::= "void" <identifier> "(" ")" <block>
<block> ::= "{" { <statement> } "}"
<statement> ::= <variable_declaration>
| <function_call> ";"
| <if_statement>
| <while_statement>
| <expression_statement>
<variable_declaration> ::= <type> <identifier> "=" <expression> ";"
<type> ::= "int" | "float" | "boolean" | "String" | "var"
<if_statement> ::= "if" "(" <expression> ")" <block> [ "else" <block> ]
<while_statement> ::= "while" "(" <expression> ")" <block>
<expression_statement> ::= <expression> ";"
<function_call> ::= <identifier> "(" [ <arguments> ] ")"
<arguments> ::= <expression> { "," <expression> }
<expression> ::= <assignment>
<assignment> ::= <comparison> [ "=" <assignment> ]
<comparison> ::= <add_sub> [ ( ">" | "<" | ">=" | "<=" | "==" | "!=" ) <add_sub> ]
<add_sub> ::= <mul_div> { ( "+" | "-" ) <mul_div> }
<mul_div> ::= <unary> { ( "*" | "/" ) <unary> }
<unary> ::= [ "!" | "-" ] <primary>
<primary> ::= <number>
| <string>
| <identifier>
| "(" <expression> ")"
<identifier> ::= <letter> { <letter> | <digit> | "_" }
<number> ::= <digit> { <digit> } [ "." <digit> { <digit> } ]
<string> ::= "\"" { <any_character_except_quote> } "\""
<letter> ::= [a-zA-Z_][a-zA-Z0-9_]*
<digit> ::= [0-9]+
<any_character_except_quote> ::= /* 任意の文字（ダブルクォートを除く） */
元々は綺麗だったけど自分の実装力が無さすぎて一つの関数の実装のため文法規則を歪めまくった結果こうなった。よくない。
でも指針にはなったので問題はなし。
3.3 実装してみる
字句解析の段階で単語単位でIDを含めて処理してるため認識した単語に対応するところに飛ばせれば問題なさそう。
例えば、statement下でintを認識した場合variable_declarationが呼び出され、そこで引数としてtype(型)とidentifier(変数名)とexpression(代入する値)をとるといった感じになります。
全部貼ると異常なコード量になるので一部だけ。
ASTobject parseFunctionCallStatement(){
Token identifier = proceedtoken();
String functionname = identifier.value;
if(!checktoken("LPAREN")){
println("'('がないよ");
return null;
}
ArrayList<ASTobject> arguments = parseArguments();
if(!checktoken("RPAREN")){
println("')'がないよ");
return null;
}
if(!checktoken("SEMICOLON")){
println("関数の';'がないよ");
return null;
}
return new FunctionCallobject(functionname,arguments);
}
//以下略
//FunctionCallStatement内の関数の引数に当たる部分をargumentとして保存する
ArrayList<ASTobject> parseArguments(){
ArrayList<ASTobject> arguments = new ArrayList<ASTobject>();
if(currenttoken().type.equals("RPAREN")){
return arguments;
}
while(true){
ASTobject expression = parseExpression();
if(expression != null){
arguments.add(expression);
}else{
println("引数の解析に失敗したよ");
return null;
}
if(checktoken("COMMA")){
continue;
}else{
break;
}
}
return arguments;
}
上記は再帰的に構造木を作っていく最たる例です。関数を認識して構造木に組み込む部分があり、その中で関数の引数部分を構造木に組み込む機能を呼び出し...とかなり綺麗に実装が行えています。
文法規則に従って他の部分も実装していきます。
ASTobject parseIfStatement(){
proceedtoken();
if(!checktoken("LPAREN")){
println("'('がないよ");
return null;
}
ASTobject condition = parseExpression();//条件文の呼び出し
if(!checktoken("RPAREN")){
println("')'がないよ");
return null;
}
ASTobject thenBlock = parseBlock();//ifで管理している実行部分の呼び出し
ASTobject elseBlock = null;
if(currenttoken() != null && currenttoken().type.equals("KEYWORD") && currenttoken().value.equals("else")){
proceedtoken();
elseBlock = parseBlock();
}
return new IfStatementobject(condition, thenBlock, elseBlock);
}
大体構文分析の実装について理解できたのでは無いでしょうか？
4. インタプリタ編
ここまではお膳立て、ようやく実行部分に移ります。
構文分析によって正しくプログラムを木構造にできたと期待して、作成した木の通りに実行を進めるプログラムを書いていきます。
4.1 方針
インタプリタでは構文木を辿って作ったノードを読み込んでそれの通りにプログラムを実行させます。
また、環境を統一するために新たにクラスを作成し、宣言時にスコープの保持もしてみる。この部分ではエラー処理なども割と大事なので想定外のエラーを起こさないように細心の注意を払っていく。
4.2 構文木をうまく使いたい
構文木をうまく利用するために、各処理に対応するクラスを作成、そこで必要な処理を変えることで実装を行なってみる。評価方法が色々なのでこれが良いかなーという判断。
また、構文木に基底クラスを作ることでプログラムを統一しつつそれぞれの処理に対応してみる。
4.3 実装してみる
インタプリタの機能は大体元のノードに対応して実行部分をクラスで管理している感じ。
環境クラスでスコープを保持。
class Environment{
HashMap<String, Object> variables;
HashMap<String, String> variableTypes;
HashMap<String, FunctionDeclarationObject> functions;
Environment(){
variables = new HashMap<String, Object>();
variableTypes = new HashMap<String, String>();
functions = new HashMap<String, FunctionDeclarationObject>();
}
void setFunction(String name, FunctionDeclarationObject function){
functions.put(name, function);
}
boolean hasFunction(String name){
return functions.containsKey(name);
}
void callFunction(String name){
if(functions.containsKey(name)){
FunctionDeclarationObject function = functions.get(name);
function.body.evaluate(this);
}else{
throw new RuntimeException("関数が定義されていないよ: " + name);
}
}
void setVariable(String name, Object value){
variables.put(name, value);
}
void setVariableType(String name, String type){
variableTypes.put(name, type);
}
Object getVariable(String name){
if(variables.containsKey(name)){
return variables.get(name);
}else{
throw new RuntimeException("変数が定義されていないよ: " + name);
}
}
String getVariableType(String name){
if(variableTypes.containsKey(name)){
return variableTypes.get(name);
}else{
throw new RuntimeException("変数の型情報がないよ: " + name);
}
}
}
インタプリタの実行部分
class Interpreter{
Environment env;
Interpreter(){
env = new Environment();
}
void interpret(ASTobject ast){
ast.evaluate(env);
}
}
実行をクラスで管理。
以下は関数の実行部分のクラス。
class FunctionCallobject extends ASTobject{
String name;
ArrayList<ASTobject> arguments;
FunctionCallobject(String name, ArrayList<ASTobject> arguments){
this.name = name;
this.arguments = arguments;
}
@Override
Object evaluate(Environment env){
// 引数の評価
ArrayList<Object> args = new ArrayList<Object>();
for(ASTobject arg : arguments){
args.add(arg.evaluate(env));
}
// 組み込み関数の実行
switch(name){
case "rect":
if(args.size() == 4){
float x = convertFloat(args.get(0));
float y = convertFloat(args.get(1));
float Width = convertFloat(args.get(2));
float Height = convertFloat(args.get(3));
rect(x, y, Width, Height);
return null;
} else {
throw new RuntimeException("rectの引数が正しくないよ");
}
case "ellipse":
if(args.size() == 4){
float x = convertFloat(args.get(0));
float y = convertFloat(args.get(1));
float Width = convertFloat(args.get(2));
float Height = convertFloat(args.get(3));
ellipse(x, y, Width, Height);
return null;
} else {
throw new RuntimeException("ellipseの引数が正しくないよ");
}
case "fill":
if(args.size() == 1){
float c = convertFloat(args.get(0));
fill(c);
return null;
} else if(args.size() == 3){
float r = convertFloat(args.get(0));
float g = convertFloat(args.get(1));
float b = convertFloat(args.get(2));
fill(r, g, b);
return null;
} else {
throw new RuntimeException("fillの引数が正しくないよ");
}
case "background":
if(args.size() == 1){
float c = convertFloat(args.get(0));
background(c);
return null;
} else if(args.size() == 3){
float r = convertFloat(args.get(0));
float g = convertFloat(args.get(1));
float b = convertFloat(args.get(2));
background(r, g, b);
return null;
} else {
throw new RuntimeException("backgroundの引数が正しくないよ");
}
default:
if(env.hasFunction(name)){
env.callFunction(name);
return null;
} else {
throw new RuntimeException("未定義の関数だよ: " + name);
}
}
}
その他実行もこんな感じで処理していく。
4.4 実行結果
こんな感じ
5. おわりに
技術の無駄遣い最高！！！！
プログラミング言語処理のとかを実装しながら学べたのでめっちゃ面白かった。もうちょい関数とか色々対応できたら公開したいなーーという所存。