私たちの言語の劣等性がすでに名前から明らかであるように、それをJSkripと呼びましょう。
さらにポスト
- 構文
- 文法
- パーサー
- 構文ツリー
- プリティプリント
構文
言語の最初のバージョンでは、
if
、
while
、および
exit
整数に対する算術構成があり
exit
。 いくつかの「事前定義関数」：印刷用の
echo()
、および
input()
用のinput
input()
。
from = 0; to = 1000;
echo( " " ,from, " " ,to, ", \n " );
while (from <= to) {
guess = (from+to)/2;
echo( " " ,guess, "? (1=, 2=, 3=) " );
i = input();
if (i==1)
to = guess-1;
else if (i==2)
from = guess+1;
else if (i==3) {
echo( "! ! \n " );
exit;
} else
echo( " ! \n " );
}
echo( ", ! \n " );
文法
サンプルプログラムを見て、言語の形式化を試みます。
PROGRAM: OPS ; //
OPS: OP | OPS OP ;
OP: '{' OPS '}' //
| EXPR ';' //
| ' if ' ' (' EXPR ')' OP
| ' if ' ' (' EXPR ')' OP ' else ' OP
| ' while ' ' (' EXPR ')' OP
| 'exit ' ' ;' ;
EXPR: NUM //
| ID //
| ID '(' ARGS ')' //
| EXPR '+' EXPR | EXPR '-' EXPR | EXPR '*' EXPR | EXPR '/' EXPR | '(' EXPR ')' | '-' EXPR //
| EXPR '==' EXPR | EXPR ' < =' EXPR | EXPR ' > =' EXPR | EXPR '!=' EXPR | EXPR '>' EXPR | EXPR '<' EXPR
| '!' EXPR // ; && *, || +
| ID '=' EXPR ; //
ARGS: //
| ARG //
| ARGS ',' ARG ;
ARG: EXPR | STRING ; //
else
、式内の演算子のグループなど、すでによく知られているあいまいな点に遭遇し
else
。 文法を修正する方法はすでに知っています。
PROGRAM: OPS ;
OPS: OP | OPS OP ;
// , else
OP1 : '{' OPS '}' | EXPR ';'
| ' if ' ' (' EXPR ')' OP1 ' else ' OP1 // if else: if else
| ' while ' ' (' EXPR ')' OP1
| 'exit ' ' ;' ;
// , if else
OP2 : ' if ' ' (' EXPR ')' OP // if else:
| IF '(' EXPR ')' OP1 ELSE OP2
| WHILE '(' EXPR ')' OP2 ;
OP: OP1 | OP2 ;
EXPR: EXPR1 | ID '=' EXPR ; //
// ,
EXPR1 : EXPR2
| EXPR1 '==' EXPR2 | EXPR1 ' < =' EXPR2 | EXPR1 ' > =' EXPR2
| EXPR1 '!=' EXPR2 | EXPR1 '>' EXPR2 | EXPR1 '<' EXPR2 ;
EXPR2 : TERM | EXPR2 '+' TERM | EXPR2 '-' TERM ;
TERM : VAL | TERM '*' VAL | TERM '/' VAL ;
VAL : NUM | '-' VAL | '!' VAL | '(' EXPR ')' | ID | ID '(' ARGS ')' ;
ARGS: | ARG | ARGS ',' ARG ;
ARG: EXPR | STRING ;
パーサー
おなじみのbisonヘッダーを追加して、文法をダミーパーサーに変換します。
%{
#include <iostream>
extern int yylineno;
extern int yylex();
void yyerror( char *s) {
std::cerr << s << ", line " << yylineno << std::endl;
exit( 1 );
}
#define YYSTYPE std::string
%}
%token IF ELSE WHILE EXIT
%token EQ LE GE NE
%token STRING NUM ID
%%
PROGRAM: OPS
;
OPS: OP
| OPS OP
;
OP1: '{' OPS '}'
| EXPR ';'
| IF '(' EXPR ')' OP1 ELSE OP1
| WHILE '(' EXPR ')' OP1
| EXIT ';'
;
OP2: IF '(' EXPR ')' OP
| IF '(' EXPR ')' OP1 ELSE OP2
| WHILE '(' EXPR ')' OP2
;
OP: OP1 | OP2 ;
EXPR: EXPR1
| ID '=' EXPR
EXPR1: EXPR2
| EXPR1 EQ EXPR2
| EXPR1 LE EXPR2
| EXPR1 GE EXPR2
| EXPR1 NE EXPR2
| EXPR1 '>' EXPR2
| EXPR1 '<' EXPR2
;
EXPR2: TERM
| EXPR2 '+' TERM
| EXPR2 '-' TERM
;
TERM: VAL
| TERM '*' VAL
| TERM '/' VAL
;
VAL: NUM
| '-' VAL
| '!' VAL
| '(' EXPR ')'
| ID
| ID '(' ARGS ')'
;
ARGS:
| ARG
| ARGS ',' ARG
;
ARG: EXPR
| STRING
;
%%
int main() { return yyparse(); }
今回は、数字ではなく文字列（
std::string
）を各トークンに保存する方が便利です。 文字値のタイプは、
YYSTYPE
マクロによって設定されます。
文法にレクサーを添付することは残っています。 行内のiskeypを認識するための名前付き状態-それには小さなトリックがあります。
私たちの言語のファイルは
jsk
と呼ばれ
jsk
。
%{
#include <string>
#define YYSTYPE std::string
#include "jsk.tab.h"
void yyerror( char *s);
%}
%option yylineno
%option noyywrap
%x STR
%%
[/][/] .*\n ; // comment
if return IF;
else return ELSE;
while return WHILE;
exit return EXIT;
== return EQ;
[<] = return LE;
>= return GE;
!= return NE;
[0-9] + { yylval = yytext ;
return NUM;
}
[a-zA-Z_][a-zA-Z0-9_] * { yylval = yytext ;
return ID;
}
["] { yylval = "" ; BEGIN (STR); }
<STR> [^\\\n"] + yylval += yytext ;
<STR> \\n yylval += '\n' ;
<STR> \\ ["] yylval += '"' ;
<STR> \\ yyerror( "Invalid escape sequence" );
<STR> \n yyerror( "Newline in string literal" );
<STR> ["] { BEGIN (INITIAL); return STRING; }
[ \t\r\n] ; // whitespace
[-{};()=<>+*/!,] { return * yytext ; }
. yyerror( "Invalid character" );
%%
宣言％xは、入力文字の読み取りの結果としてではなく、
BEGIN(STR)
明示的な呼び出しの結果としてレクサーが入力する名前付き状態を定義します。 初期状態は
INITIAL
と呼ばれます。 それに戻るには、
BEGIN(INITIAL)
呼び出します。 その結果、レクサーには2つの異なる正規表現セットがあります。1つはメインプログラム用、もう1つは文字列リテラル用です。 引用ごとに、2つのセットを切り替えます。
結果のダミーパーサーは、プログラム内の構文エラーを探します。 そうでない場合は、何も出力しません。
[tyomitch@home ~]$ lex jsk.lex
[tyomitch@home ~]$ bison -d jsk.y
[tyomitch@home ~]$ c++ lex.yy.c jsk.tab.c
[tyomitch@home ~]$ ./a.out < test.jsk
[tyomitch@home ~]$ ./a.out
{ foo();
bar; }
}
syntax error, line 3
構文ツリー
ルールの畳み込みに役立つものは何ですか？
過去には、畳み込み中、解析中に、必要なすべてのアクションを実行できました（式の値を計算します）。
より普遍的なアプローチは、テキストの構文構造に対応する入力テキストのツリーを構築し、解析が完了した後、このツリーを処理することです。 ツリーから情報を取得するための非コンパイルメソッドが多数あります：再帰的なクロールからXPathクエリまで。
ツリーの各ノードタイプに個別のクラスを定義し、パーサースタックにノードオブジェクトへのポインターを格納します。 それらに加えて、スタックには、レクサーからの行と、「中間結果」が含まれている場合があります。このため、ツリー内の別のノードを選択しないことにします。 この例では、ツリーノードは
ARGS
シンボルに対応していません。すべての関数引数へのリンクを「関数呼び出し」ノードに直接保存します。 つまり、構文ツリーは解析ツリーと完全に一致する必要はありません。 より便利に再構築する権利があります。 不一致の別の例は、構文ツリーに「演算子」ノードがないことです。 「演算子のリスト」のみ-おそらく1つの要素から。
%{
#include <iostream>
#include <list>
extern int yylineno;
extern int yylex();
void yyerror( char *s) {
std::cerr << s << ", line " << yylineno << std::endl;
exit( 1 );
}
class oper_t { // abstract
protected : oper_t() {}
public : virtual ~oper_t() {}
};
class expr_t { // abstract
protected : expr_t() {}
public : virtual ~expr_t() {}
};
class block : public oper_t {
std::list<oper_t*> ops;
void append(oper_t* op) {
block* b = dynamic_cast <block*>(op);
if (b) {
ops.splice(ops.end(), b->ops, b->ops.begin(), b->ops.end());
delete b;
}
else ops.push_back(op);
}
public :
block() {}
block(oper_t* op) { append(op); }
block(oper_t* op1, oper_t* op2) { append(op1); append(op2); }
};
class exprop : public oper_t {
expr_t* expr;
public : exprop(expr_t* expr) : expr(expr) {}
};
class ifop : public oper_t {
expr_t* cond;
block thenops, elseops;
public : ifop(expr_t* cond, oper_t* thenops, oper_t* elseops) :
cond(cond), thenops(thenops), elseops(elseops) {}
};
class whileop : public oper_t {
expr_t* cond;
block ops;
public : whileop(expr_t* cond, oper_t* ops) : cond(cond), ops(ops) {}
};
class exitop : public oper_t {};
class binary : public expr_t {
const char * op;
expr_t *arg1, *arg2;
public : binary( const char * op, expr_t *arg1, expr_t *arg2) :
op(op), arg1(arg1), arg2(arg2) {}
};
class assign : public expr_t {
std::string name;
expr_t* value;
public : assign( const std::string& name, expr_t* value) :
name(name), value(value) {}
};
class unary : public expr_t {
const char * op;
expr_t* arg;
public : unary( const char * op, expr_t* arg) : op(op), arg(arg) {}
};
class funcall : public expr_t {
std::string name;
std::list<expr_t*> args;
public : funcall( const std::string& name,
const std::list<expr_t*>& args) :
name(name), args(args) {}
};
class value : public expr_t {
std::string text;
public : value( const std::string& text) : text(text) {}
};
// : , , ,
typedef struct {
std::string str;
oper_t* oper;
expr_t* expr;
std::list<expr_t*> args;
} YYSTYPE;
#define YYSTYPE YYSTYPE
//
std::string replaceAll( const std::string& where, const std::string& what, const std::string& withWhat) {
std::string result = where;
while ( 1 ) {
int pos = result.find(what);
if (pos==- 1 ) return result;
result.replace(pos, what.size(), withWhat);
}
}
%}
%token IF ELSE WHILE EXIT
%token EQ LE GE NE
%token STRING NUM ID
%type < str > ID NUM STRING
%type < oper > OPS OP1 OP2 OP
%type < expr > EXPR EXPR1 EXPR2 TERM VAL ARG
%type < args > ARGS
%%
PROGRAM: OPS //
;
OPS: OP // inherit
| OPS OP { $$ = new block( $1 , $2 ); }
;
OP1: '{' OPS '}' { $$ = $2 ; }
| EXPR ';' { $$ = new exprop( $1 ); }
| IF '(' EXPR ')' OP1 ELSE OP1 { $$ = new ifop( $3 , $5 , $7 ); }
| WHILE '(' EXPR ')' OP1 { $$ = new whileop( $3 , $5 ); }
| EXIT ';' { $$ = new exitop(); }
;
OP2: IF '(' EXPR ')' OP { $$ = new ifop( $3 , $5 , new block()); }
| IF '(' EXPR ')' OP1 ELSE OP2 { $$ = new ifop( $3 , $5 , $7 ); }
| WHILE '(' EXPR ')' OP2 { $$ = new whileop( $3 , $5 ); }
;
OP: OP1 | OP2 ; // inherit
EXPR: EXPR1 // inherit
| ID '=' EXPR { $$ = new assign( $1 , $3 ); }
EXPR1: EXPR2 // inherit
| EXPR1 EQ EXPR2 { $$ = new binary( "==" , $1 , $3 ); }
| EXPR1 LE EXPR2 { $$ = new binary( "<=" , $1 , $3 ); }
| EXPR1 GE EXPR2 { $$ = new binary( ">=" , $1 , $3 ); }
| EXPR1 NE EXPR2 { $$ = new binary( "!=" , $1 , $3 ); }
| EXPR1 '>' EXPR2 { $$ = new binary( ">" , $1 , $3 ); }
| EXPR1 '<' EXPR2 { $$ = new binary( "<" , $1 , $3 ); }
;
EXPR2: TERM // inherit
| EXPR2 '+' TERM { $$ = new binary( "+" , $1 , $3 ); }
| EXPR2 '-' TERM { $$ = new binary( "-" , $1 , $3 ); }
;
TERM: VAL // inherit
| TERM '*' VAL { $$ = new binary( "*" , $1 , $3 ); }
| TERM '/' VAL { $$ = new binary( "/" , $1 , $3 ); }
;
VAL: NUM { $$ = new value( $1 ); }
| '-' VAL { $$ = new unary( "-" , $2 ); }
| '!' VAL { $$ = new unary( "!" , $2 ); }
| '(' EXPR ')' { $$ = $2 ; }
| ID { $$ = new value( $1 ); }
| ID '(' ARGS ')' { $$ =new funcall( $1 , $3 ); }
;
ARGS: { $$ .clear(); }
| ARG { $$ .clear(); $$ .push_back( $1 ); }
| ARGS ',' ARG { $$ = $1 ; $$ .push_back( $3 ); }
;
ARG: EXPR // inherit
| STRING { $$ =new value( '"' +replaceAll( $1 , " \n " , " \\ n" )+ '"' ); }
;
%%
int main() { return yyparse(); }
%type<str>
宣言は、
YYSTYPE
フィールドを文字値として使用するかを文法文字（端末と非端末）に指定します。 このフィールドが指定されている場合、バイソンは$タグがそのような文法記号を参照するたびにそれを置き換えます。 （前の例のように）フィールドが指定されていない場合、
YYSTYPE
全体
YYSTYPE
使用されます。
従来のsysherパーサーでは、
YYSTYPE
union
として宣言されていました。各文字は独自の方法で同じ格納された値を解釈します。 これは私たちには適していません。デストラクタを持つオブジェクトは
union
フィールドにはなれません。 したがって、
YYSTYPE
を構造体として宣言します。シンボルに不要な構造体フィールドは、メモリを無駄に占有するだけです。 しかし、私たちは貪欲ではありません。
不快な瞬間は、
else
との競合を修正するために、2つの同一の
if..else
ルールと2つの同一の
while
ルールが文法に現れたことです。 どちらがより不快かを選択することは私たちの良心です：
else
と）に優先順位を設定することは、あたかもオペレーターであるかのように。 または、畳み込みコードを2回コピーして貼り付けます。
そのため、パーサーはメモリ内にツリーを構築し、準備ができたら、メモリを解放することなくそのまま残します。 あまり印象的ではありませんか？
プリティプリント
パーサーが何か有意義なことをするための努力はほとんど必要ありません。 たとえば、式に括弧を入れて、冗長な{}を削除し、さらに、ステートメントをBSDカーネル標準形式に合わせました。
ツリークラスに再帰的なリストを追加します。
クラス定義のみが変更され、
PROGRAM
文字コンボリューションが変更されます。
#define TOKENPASTE(x, y) x ## y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)
#define foreach(i, list) typedef typeof(list) TOKENPASTE2(T, __LINE__ ); \
for (TOKENPASTE2(T, __LINE__ )::iterator i = list.begin(); i != list.end(); i++)
class oper_t { // abstract
protected : oper_t() {}
public : virtual ~oper_t() {}
virtual void print( int indent= 0 ) = 0 ;
};
class expr_t { // abstract
protected : expr_t() {}
public : virtual ~expr_t() {}
virtual void print() = 0 ;
};
class block : public oper_t {
std::list<oper_t*> ops;
void append(oper_t* op) {
block* b = dynamic_cast <block*>(op);
if (b) {
ops.splice(ops.end(), b->ops, b->ops.begin(), b->ops.end());
delete b;
}
else ops.push_back(op);
}
public :
block() {}
block(oper_t* op) { append(op); }
block(oper_t* op1, oper_t* op2) { append(op1); append(op2); }
int size() { return ops.size(); }
virtual void print( int indent= 0 ) {
foreach(i, ops) {
std::cout << std::string(indent, '\t' );
(*i)->print(indent);
}
}
virtual ~block() { foreach(i, ops) delete *i; }
};
class exprop : public oper_t {
expr_t* expr;
public : exprop(expr_t* expr) : expr(expr) {}
virtual void print( int indent= 0 ) {
expr->print();
std::cout << ";" << std::endl;
}
virtual ~exprop() { delete expr; }
};
class ifop : public oper_t {
expr_t* cond;
block thenops, elseops;
public : ifop(expr_t* cond, oper_t* thenops, oper_t* elseops) :
cond(cond), thenops(thenops), elseops(elseops) {}
virtual void print( int indent= 0 ) {
std::cout << "if " ; cond->print(); std::cout << " {" << std::endl;
thenops.print(indent+ 1 );
if (elseops.size()) {
std::cout << std::string(indent, '\t' ) << "} else {" << std::endl;
elseops.print(indent+ 1 );
}
std::cout << std::string(indent, '\t' ) << "}" << std::endl;
}
virtual ~ifop() { delete cond; }
};
class whileop : public oper_t {
expr_t* cond;
block ops;
public : whileop(expr_t* cond, oper_t* ops) : cond(cond), ops(ops) {}
virtual void print( int indent= 0 ) {
std::cout << "while " ; cond->print(); std::cout << " {" << std::endl;
ops.print(indent+ 1 );
std::cout << std::string(indent, '\t' ) << "}" << std::endl;
}
virtual ~whileop() { delete cond; }
};
class exitop : public oper_t {
virtual void print( int indent= 0 ) { std::cout << "exit;" << std::endl; }
};
class binary : public expr_t {
const char * op;
expr_t *arg1, *arg2;
public : binary( const char * op, expr_t *arg1, expr_t *arg2) :
op(op), arg1(arg1), arg2(arg2) {}
virtual void print() {
std::cout<< "(" ;
arg1->print();
std::cout<<op;
arg2->print();
std::cout<< ")" ;
}
virtual ~binary() { delete arg1; delete arg2; }
};
class assign : public expr_t {
std::string name;
expr_t* value;
public : assign( const std::string& name, expr_t* value) :
name(name), value(value) {}
virtual void print() { std::cout<<name<< " = " ; value->print(); }
virtual ~assign() { delete value; }
};
class unary : public expr_t {
const char * op;
expr_t* arg;
public : unary( const char * op, expr_t* arg) : op(op), arg(arg) {}
virtual void print() { std::cout<<op; arg->print(); }
virtual ~unary() { delete arg; }
};
class funcall : public expr_t {
std::string name;
std::list<expr_t*> args;
public : funcall( const std::string& name,
const std::list<expr_t*>& args) :
name(name), args(args) {}
virtual void print() {
std::cout<<name<< "(" ;
foreach(i,args) {
if (i!=args.begin())
std::cout<< ", " ;
(*i)->print();
}
std::cout<< ")" ;
}
virtual ~funcall() { foreach(i,args) delete *i; }
};
class value : public expr_t {
std::string text;
public : value( const std::string& text) : text(text) {}
virtual void print() { std::cout<<text; }
};
PROGRAM: OPS { $1 - > print(); delete $1 ; }
;
何が起こったのかを確認してください：
[tyomitch@home ~]$ lex jsk.lex
[tyomitch@home ~]$ bison -d jsk.y
[tyomitch@home ~]$ c++ jsk.tab.c lex.yy.c
[tyomitch@home ~]$ ./a.out < test.jsk
from = 0;
to = 1000;
echo(" ", from, " ", to, ", \n");
while (from <= to) {
guess = ((from + to) / 2);
echo(" ", guess, "? (1=, 2=, 3=) ");
i = input();
if (i == 1) {
to = (guess - 1);
} else {
if (i == 2) {
from = (guess + 1);
} else {
if (i == 3) {
echo("! !\n");
exit;
} else {
echo(" !\n");
}
}
}
}
echo(", !\n");
入力テキストのフォーマットされたリストは、パーサーを最初にチェックする一般的な方法です。 投稿の最初からのサンプルコードは、この点であまり成功していません。 すべての言語構成からはほど遠い。 ただし、テスト用ではなく、言語を説明するためのものです。
テキストをフォーマットするために、ツリーに煩わされることは意味がないことは明らかです。各演算子のスタックにテキスト行のリストを保存し、インデントを追加して畳み込みでこれらの行をマージするだけで十分です。 なぜ、インデントのために、バイソンも必要ないのです。そして、flexはそれをします。 （括弧はもう少しおもしろいですが。）
次回は、バイソンから休憩します。