これはしばらくの間私の心にありました。私は再帰降下パーサーに興味を持っており、その実装方法を知りたいと思っています。私が欲しいのは、「5+5」や「(5+5)*3」などの単純な算術演算を理解できる単純なパーサーです。
最初のステップは、入力文字列全体を取得して多くの部分文字列に分割する「トークナイザー」を作成することだと思います。私が行ったこの部分 (私はそれについてここで尋ねなければなりませんでした。ここにも関連コードを投稿しているので、したくない場合はリンクをたどる必要はありません。)私の、私は の 、またはトークンで終わりvectorますstring。ここで難しいのは、これらのトークンを解析したいということです。
ウィキペディアの recursive descent parsers に関する記事を読みました。全体的な概念は理解できますが、いつものように、実装は少しわかりにくいです。その記事には、非常に単純なプログラミング言語用の再帰降下パーサーの C 実装があり、記事でも説明されています。私はそのコードをできる限り研究し、基本的に同じことを書き込もうとしましたが、それは自分のプログラムのためでした。以下がそのコードです。
私が本当に混乱しているのは、このパーサーが何をするかです。プログラムを通過し、文法の特定の部分を「期待」しているようです。しかし、それがそこに到達すると、それは何をしますか? たとえば、「用語」を解析することになっているウィキペディア コードの 1 つの関数を次に示します。
void term(void) {
factor();
while (sym == times || sym == slash) {
getsym();
factor();
}
}
これは、次の文法を解析するためのものです。
term = factor {("*"|"/") factor} .
これは理にかなっています。しかし、それは実際の用語で何をしますか? その用語が単に「6」である、または「3*2」であり、値が 6 であることが判明したとしましょう。それを残りの入力にどのように組み込むのでしょうか? (6 を返すために) の代わりにterm()a を返すべきではありませんか? それとも他の方法で行われますか？doublevoid
また、このようなパーサーでコードを出力することと、入力に対してすぐに動作すること (つまり、コンパイラーとインタープリター) の違いは何でしょうか? これら 2 つ (少なくともこの例では) は理論的には同じ方法で実装されていますか、それとも根本的に異なっていますか?
任意の入力を歓迎します。これまでの私のコードは次のとおりです。
#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>
#include <sstream>
using namespace std;
vector<string> symbolize(string);
bool accept(string);
void getSymbol();
void error(string s);
bool expect(string);
void expression();
void term();
void factor();
int currentPosition = -1;
string symbol;
vector<string> symbols;
int main(int argc, const char * argv[])
{
string input;
getline(cin,input);
symbols = symbolize(input);
getSymbol();
expression();
return 0;
}
void factor(){
if(isdigit(symbol.c_str()[0])){}
else if(accept("(")){
expression();
expect(")");
}
else {
error("Syntax error");
}
}
void term(){
factor();
while(symbol=="*"||symbol=="/"){
getSymbol();
factor();
}
}
void expression(){
if(symbol == "+" || symbol == "-") getSymbol();
term();
while(symbol == "+" || symbol == "-"){
getSymbol();
term();
}
}
void error(string s){
cout << endl << "ERROR: " << s << endl;
}
void getSymbol(){
currentPosition++;
if(currentPosition>=symbols.size())error("Unexpectedly reached end of input");
}
bool expect(string s){
if(accept(s))return true;
else error("Expected '" + s + "'");
return false;
}
bool accept(string s){
if(s==symbol){getSymbol();return true;}
return false;
}
// Takes a string and breaks it into substrings
vector<string> symbolize(string input){
int position = 0;
char c;
//stringstream s;
vector<string> symbols;
enum symbolType {TEXT,OPERATOR}symbolType,charType;
while(position < input.size()){
stringstream s;
c = input.at(position);
if(isalnum(c))symbolType = TEXT;
else symbolType = OPERATOR;
charType = symbolType;
while(symbolType == charType){
s << c;
position++;
if(position>=input.length())break;
c = input.at(position);
if(isspace(c)||c=='\n'){position++; break;}
if(isalnum(c)) charType = TEXT;
else charType = OPERATOR;
}
symbols.push_back(s.str());
}
return symbols;
}
編集:私のコードは常にERROR: syntax error関数から: を出力することに言及する必要がありfactor()ます。