Parseg

文脈自由文法(CFG)で記述された生成規則に基づいて、LL1構文表をC/C++言語のソースに翻訳するプログラムです。構文表の他に、意味解析ルーチンの雛形ソースも出力しますが、この意味解析部の雛形は、ひとつの例として出力するものです。

インストール

ダウンロードページから、「ParsegSetup.zip」を適当なフォルダにダウンロードし、そこでzipファイルを展開すると「ParsegSetup」フォルダが作成されます。、その中に、「setup.exe」がありますので、それを実行し、画面に従ってインストールして下さい。以下の説明に使用しているファイルは、すべてサンプルとして入っています。

実行画面と生成ファイル

Parsegの画面は、大変簡単なもので、表示内容は生成規則のデバッグのためにあります。画面の左から、読込んだトークンコード、"First"集合、生成規則コード表です。

左上の「ルールファイルの選択」をクリックするとファイル選択のダイアログが表示されますので、ルールファイル(拡張子は～.rul)を指定します。

サンプルとして入っているルールファイル「Synju-0.rul」を選択すると、右画面のように各内容が表示され、(1)～(7)のようなファイルが、同じフォルダ内に生成されます。

ルールファイル名の付け方には次のようにしてください。「任意の名前-数字.rul」のように、ハイフンとルールのバージョン番号を付加して下さい。（※例えば、「rule-1.0.2.rul」のように。）

同じフォルダ内に保存されるファイルは、プリフィックスとして、「PG-数字-」の付加した名前となります。

(1) PG-xxx-ParsingTableSize.h

(2) PG-xxx-ParsingTable.h

(3) PG-xxx-ParsingTable.cpp

(4) PG-xxx-SemanticsDef.h

(5) PG-xxx-Semantics.h

(6) PG-xxx-Semantics.cpp

(7) PG-xxx-First.txt、PG-xxx-Follow.txt,PG-xxx-RuleList.txt

「xxx」の部分は、入力ファイルの「rule-xxx.rul」の「xxx」と同じ様に設定されます。(3)が構文表ソースで、(1)、(2)は、その中の「#include」文に指定されています。また、(6)が意味解析部ソースで、(4)～(5)は、その中の「#inlucde」文に指定されています。(7)の３つのファイルは、デバッグ用途に使用する補助的なものです。非終端子のFirst集合、非終端子のFollow集合、そして生成規則の表です。※これらの自動生成されたファイルは、実行するたびに上書きされますので、ご注意ください。このソースを改造せずにコピーしてお使いください。

生成規則の記述方法

入力となるルールファイル(生成規則)の記述方法の例を以下に示します。

ここは、コメント欄になります。

%token
%include "Synju-0-term.inc"							(2) 終端子トークンコード表
%include "Synju-0-nterm.inc"						(2) 非終端子トークンコード表
%end

Roots			-> Object ObjectList .				(3) Rootsは、出発シンボル
ObjectList		-> ";" Object ObjectList2 .			(4) Object等は非終端子
				-> @ .
ObjectList2		-> ObjectList .
Relation		-> Object RelationList .
RelationList	-> ";" Object RelationList2 .
				-> @ .
RelationList2	-> RelationList .
Object			-> ObjectName Initializer Attribute Enum .
ObjectName		-> Qualident .
				-> @ .
Qualident		-> "$ident"  QualidentList .			(4) "$ident"は、終端子。　
QualidentList	-> "." "$ident"  QualidentList2 .
				-> @ .
QualidentList2	-> QualidentList .					(5) ここもコメント欄になります。
Attribute		-> "$value" .						(4) "$vale"は、終端子
				-> "EMPTY" .							: reserve word
				-> Qualident .
				-> @ .
Initializer		-> "=" .
				-> @ .								(6)'@'がある場合、Initializerは「指定無し」を許容する
Enum			-> "[" Relation "]" .				: local description
				-> @ .								(7) "Enum -> @ ."のようには書かない

(1) %tokenまでは、コメント欄になります。

(2) %endまでに、%include文があれば、それを取り込みます。右の"Synju-0-term.inc"は終端子のトークンコード表で、"Synju-0-nterm.inc"は非終端子のトークンコード表です。

(3) 最初に現れる識別子が出発シンボルになります。

(4) 英文字列は非終端子で、終端子は""で囲みます。

(5) 1行の規則はピリオド"."で終わり、それ以降はコメントになります。

(6) 導出マークは"->"で、＠は、「空」を許す意味です。

(7) 生成規則の左側・非終端子は、最初に出現するものだけに記述し、複数の規則がある場合は"->"で始まります。

※シンタックス等の細かなエラーチェックはしておりませんので、ご了承ください。

 

トークンコード・ファイル

インクルードされている「非終端子」、「終端子」のトークンコードファイルは、次のような形式です。

//　非終端子トークンコード表
// +-----------+---------+
// |  keyword  | code    |
// +----1------+--2------+
Roots			1001
Object			1002
ObjectList		1003
ObjectList2		1004
Relation		1005
RelationList	1006
RelationList2	1007
ObjectName		1008
Attribute		1009
Enum			1010
Qualident		1011
QualidentList	1012
QualidentList2	1013
Initializer		1014
@				9999	empty token code

// 終端子トークンコード表
// +----------+---------+
// | keyword  |  code	|
// +---1------+--2------+
EMPTY			1
$ident			11
$value			21
.				31
;				32
[				33
]				34
=				35	OP_DEF
$$				36	token-end

ここでの注意点は、非終端子のトークンコードは1001から始まるように指定し、@は9999に指定するようにして下さい。これらの生成規則のファイルを読み込み、構文表ソース、意味解析部ソースを出力します。

構文表

PG-xxx-ParsingTable.cppが出力されたソースですが、GetRuleNumber、GetRule、InitParsingTableという3つの関数があるのみで、構文表の実体は、PG-xxx-ParsingTable.hにあり、staticなグローバル配列になっています。"InitParsingTable"関数は、構文表の初期化、設定するものですので、最初に呼び出さなければなりません。これらのソースを改良して各自の構文解析部に取り込む事ができます。

構文解析

生成された構文表と意味解析サンプルソースを使った、構文解析の擬似コードを示します。

PG-x-ParsingTable.cppにある関数、InitParsingTable関数、GetRuleNumber関数、GetRule関数の使い方、そして、意味解析部の雛形サンプルであるPG-x-Semantics.cppにあるSemantics関数は、以下のような構文解析部(擬似コード)を想定して生成されています。

(*1),(*2),(*3)が、PG-x-ParsingTable.cppの関数、(*4)が、PG-x-Semantics.cppの関数です。以下は使用サンプルとしての擬似コードですので、様々なエラーチェック処理やエラー回復処理は省かれています。意味解析部をどこに置くかなどは、各自の処理によって異なるでしょう。メンバー変数なども仮定のもので、未定義の変数なども含まれています。例えば、CLioクラスが使われていますが、GetTokenの引数に渡されていますので、ファイル読み込み用の独自クラスを意味しているとでも解釈してください。構文スタック処理や、場合によっては解析用スタックや意味解析のためのスタックなどが必要になるかもしれません。

class CParse
{ private:
	CTable*	m_pcsKey;    				// キーワードテーブル
	CLex*	m_pcsLex;    				// 字句解析部
	CSeman*	m_pcsSeman;  				// 意味解析部
  public:
	CParse();
	~CParse();
	int	m_nRuleCode;

	int	Load(CLio& csFi);				// 読込み
	int	Reduce(int* rladr,CStack* stk);	// 解析
};
CParse::
CParse()
{	::InitParsingTable();				// (*1) 構文表の初期化
	m_pcsKey	= new CTable();			// キーワードテーブル生成
	m_pcsLex	= new CLex();			// 字句解析部の初期化
	m_pcsSeman	= new CSemantics();		// 意味解析部の初期化
}
CParse::
~CParse()
{	delete m_pcsLex;
	delete m_pcsKey;
	delete m_pcsSeman;
}
int CParse::
Load(CLio& csFi)
{	int nToken,nInput,nTail,nError,*pnRecover;

	CStack*    
	pcsStk = new CStack(200);			// 200個の構文スタック
	pcsStk->Push(g_nTcEnd);				// トークンEND設定
	pnRecover = pcsStk->Under();		// for error recovery
	pcsStkA->Push(pnRecover,-1);		// 初期化

	pcsStk->Push(NT_START);				// Starting NonTerminal
	pnRecover = pcsStk->Under();		// for error recovery
	pcsStkA->Push(pnRecover,-1);		// 初期化

	nToken = nTail = nError = 0;
	nInput = m_pcsLex->GetToken(m_pcsKey,csFi);

	do
	{	//$$-------------------
		//$$ 意味解析部
		//$$
		//$$    X ->  A  B  C
		//$$         ↑ ↑ ↑ ↑
		//$$ nTail:  3  2  1  0
		//$$--------------------
		nTail  = pcsStk->RuleIndex();
		nError = m_pcsSeman->Semantics(	nTail,
										処理中の「ルール番号」,
										m_pcsLex);	// (*4)
		if(nError)
		{	// エラー処理
		}

		//$$------------
		//$$ 構文解析部
		//$$------------
		nToken = pcsStk->Look();
		if(nToken <  NON_TERMINAL)
		{	if(nToken == nInput)    	// 構文スタック最上段が終端子の場合
			{	pcsStk->Pop();      	// 構文スタックPOP
				nInput = m_pcsLex->GetToken(m_pcsKey,csFi);
			}
			else
			{   delete pcsStk;
				return ERR_COMPILER;
			}
		}
		else
		{	// (*2) 生成規則の選択
			int* pnRuleAdr = ::GetRule(nToken,nInput);
			if(pnRuleAdr != NULL) 		// 生成規則があれば
			{	// (*3)ルール番号の取得
				m_nRuleCode = ::GetRuleNumber(pnRuleAdr);
				// Reduce実行
				nToken = Reduce(pnRuleAdr,pcsStk);
			}
			else
			{	if(nToken == NT_EMPTY)
				{	pcsStk->Pop();		// 構文スタックPOP
				}
				else
				{	// シンタックスエラー
					delete pcsStk;
					return ERR_SYNTAX;
				}
			}
		}
	} while(nToken != g_nTcEnd);

	delete pcsStk;
	return 0;        
}
int CParse::
Reduce(int* rladr,CStack* stk)
{	int* topp = rladr;
	int* rlp  = rladr;
	while(*rlp != 0)    // 生成規則の最後(0)まで
	{   rlp++;
	}
	rlp--;              // 最後のひとつ前(生成規則の最後のトークン)
	stk->Pop();
	while(rlp != topp)
	{	int* pnSp = stk->Push(*rlp);
		ASSERT( pnSp != NULL);
		rlp--;
	}
	int* pnSp = stk->Push(*rlp);
	ASSERT( pnSp != NULL);
	return *rlp ;
}

意味解析用サンプルソース

自動生成されたPG-xxx-Semantics.cppが意味解析用に使うサンプルソースです。一例に過ぎませんので、意味解析部は、各自の構文解析部に合わせて作成して下さい。

このPG-xxx-Semantics.cppは、以下のように各構文に従った意味解析処理をすることを想定しています。m_pcsStkOpなどは意味解析用のスタックとして使用しています。

//$$=======================================
//$$ Relation  ->  Object  RelationList
//$$     (nTail:  ^2      ^1           ^0)
//$$=======================================
int CSemantics::
M_Relation0(int nTail,int nRuleNo,CLex* pcsLex)
{	//------------------------------------------------
	// Objectの並びでは同じスコープであり、それを保障する。
	// -----------------------------------------------
	if(nTail == 2)
	{	CIdentDict* pcsParentIdent = GetScopeStartIdent();
		// Push    -- 現在のスコープIdentを保存する
		void** csOp = m_pcsStkOp->Push(pcsParentIdent);
		ASSERT( csOp != NULL);
	}
	if(nTail == 1)
	{	CIdentDict*  pcsParentIdent;
		// Pop
		m_pcsStkOp->Pop((void**)&pcsParentIdent);	// スコープIdentの取得
		SetScopeStartIdent(pcsParentIdent);			// スコープ再設定
	}
	return 0;
}

この雛形サンプルは自動生成されたものですので、PG-xxx-Semantics.cppを使用せずに、各自が作成された意味解析部を使うこともできます。PG-xxx-Semantics.cpp自体は自動生成するたびに上書きされてしまいますのでご注意ください。

Synju-0ページへ