言語処理系

言語処理系(compiler 編訳系)の構造

1. 語句解析
2. 構文解析
3. 意味解析
4. コード生成

素語を文字から構成する規則 ... 正規文法(regular grammar)
正規表現 (regular expression)の例

名標

[A-Za-z_][0-9A-Za-z_]*

整定数

[1-9][0-9]*

• 有限オートマトンの動作をプログラムの制御の流れに よって実現し、付加的な処理を埋め込む。
• 有限オートマトンの状態遷移表を参照しながら制御する 機構をプログラムによって実現する。このプログラムは 言語にはよらないので、状態遷移表と付加的な処理を言語ごと に用意する。

• c = getchar();
  while (c == ' ') c = getchar();
  switch (c)
        英字:{
          zzleng = 0;
          do {
            zztext[zzleng] = c;
            zzleng++;
            c = getchar();
          } while (cが英字でも数字でもない);
          backchar(c);
          zzlex = IDENTIFIER;
          zzlval = install(zztext,zzleng);
        }
        数字: ....
        ....
        '+': zzlex = PLUS;
        ....
  
  

• %%
   ' '+    { REJECT }
   [a-zA-Z][a-zA-Z0-9]*
           { yylval = install(yytext,yyleng);
             return(IDENTIFIER);
           }
   [0-9]+  { ... }
   ...
   [+]     { return(PLUS) }
  ....
  %%
  

文法にもとづく導出による生成ができるかどうかの解析
解析方法

下降型解析法

系統木の根から葉に向かって木を構成していく

上昇型解析法

葉から根に向かう。導出の逆の過程＝還元(reduction)

再帰下降型解析法

導出での例「式」は最右導出。 最左導出では
式 => 項 => 項*式 => 係数*式 => 名標*式 => 名標*項 => 名標*係数 => 名標*(式) => 名標*(式+項) => 名標*(項+項) => 名標*(係数+項) => 名標*(名標+項) => 名標*(名標+係数) => 名標*(名標+名標)
のようになる。

「式」の構文規則を変更し、再帰的な解析法を適用したプログラム例を示す。

procedure E();
  begin T();
    while token = '+' do
      begin gettoken(); T() end
  end;
procedure T();
  begin F();
    while token = '*' do
      begin gettoken(); F() end
  end;
procedure F();
  begin
    if token = '(' then
      begin gettoken(); E();
        if token <> ')' then error();
      end
    else if token = 'i' then gettoken()
    else error();
  end;

 E -> T, E -> T + T,
 T -> F, T -> F * F,
 F -> ( E ), F -> i

L .. 左から素語を調べる
L .. 最左導出
(1) .. 1個の先読み

予測型解析法

repeat
  s:=スタック最上段の状態;
  a:=つぎに調べようとしている素語;
  if A[s,a]=shift then
    begin t:=G[s,a];
      スタックにaとtとをtが最上段に
      くるように押し込み、入力素語列
      からaを取り除く
    end
  else if A[s,a]=reduce X->Y1Y2...Yk then
    begin スタックからk個の状態とk個の
          記号を取り出す;
      u:=スタック最上段の状態;
      t:=G[u,X];
      スタックにXとtとをtが最上段に
      くるように押し込む
    end
  else if A[s,a]=accept then 解析終了
  else 誤り
forever;

「式」の構文規則としては、

1. E -> E+T
2. E -> T
3. T -> T*F
4. T -> F
5. F -> (E)
6. F -> i

解析表

			A							G
状態	+	*	(	)	i	$		+	*	(	)	i	$	E	T	F
0			s		s					4		5		1	2	3
1	s					a		6
2	2	s		2		2			7
3	4	4		4		4
4			s		s					4		5		8	2	3
5	6	6		6		6
6			s		s					4		5			9	3
7			s		s					4		5				10
8	s			s				6			11
9	1	s		1		1			7
10	3	3		3		3
11	5	5		5		5

解析例

スタック	素語の列	動作
----------------	----------	------
$0	i*(i+i)$	shift
$0i5	*(i+i)$	reduce 6
$0F3	*(i+i)$	reduce 4
$0T2	*(i+i)$	shift
$0T2*7	(i+i)$	shift
$0T2*7(4	i+i)$	shift
$0T2*7(4i5	+i)$	reduce 6
$0T2*7(4F3	+i)$	reduce 4
$0T2*7(4T2	+i)$	reduce 2
$0T2*7(4E8	+i)$	shift
$0T2*7(4E8+6	i)$	shift
$0T2*7(4E8+6i5	)$	reduce 6
$0T2*7(4E8+6F3	)$	reduce 4
$0T2*7(4E8+6T9	)$	reduce 1
$0T2*7(4E8	)$	shift
$0T2*7(4E8)11	$	reduce 5
$0T2*7F10	$	reduce 3
$0T2	$	reduce 2
$0E1	$	accept

上の構文規則を yacc で書いて、yacc -v コマンドを用いると y.output というファイルができる。

宣言の処理

ブロック構造を持つ言語では、あらたな ブロックに入るたびに名標を管理する表が作成され、ブロック から出る時に消滅する。

式・文の処理

データ型の適合性、飛び越し先の適合性。

記憶場所の割り当て

プログラムが実行される時の静的な変数領域

• 最適化
• 引数結合(値呼び出し、変数呼び出し)
• メモリー操作。動的割り付け(system call)