CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

Recursive descent parser generator

From Rosetta Code
Recursive descent parser generator is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Write a recursive descent parser generator that takes a description of a grammar as input and outputs the source code for a parser in the same language as the generator. (So a generator written in C++ would output C++ source code for the parser.) You can assume that all of the rules have been preprocessed into a form suitable for the construction of a recursive descent parser. Check the following links for more details.

Use the parser generator and a grammar file to build a parser that takes an arithmetic expression and turns it in to three address code. The resulting parser should take this (or something similar) as input:

(one + two) * three - four * five

And generate this (or something similar) as output:

_0001 = one + two
_0002 = _0001 * three
_0003 = four * five
_0004 = _0002 - _0003

C++[edit]

Works with: C++11

This program translates an annotated LL(1) grammar into a C++ lexer plus parser. Each rule is required to return a string of some kind and the return values of the already matched nonterminals (and matched text of terminals) can be accessed with $1, $2, etc. which are replaced by the appropriate string variable.

It can't handle newlines as part of the grammar, the error checking is fairly limited and the error reporting is basically non-existent, but the parser it generates (not shown below) is human readable.

 
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <regex>
using namespace std;
 
map<string, string> terminals;
map<string, vector<vector<string>>> nonterminalRules;
map<string, set<string>> nonterminalFirst;
map<string, vector<string>> nonterminalCode;
 
int main(int argc, char **argv) {
if (argc < 3) {
cout << "Usage: <input file> <output file>" << endl;
return 1;
}
 
ifstream inFile(argv[1]);
ofstream outFile(argv[2]);
 
regex blankLine(R"(^\s*$)");
regex terminalPattern(R"((\w+)\s+(.+))");
regex rulePattern(R"(^!!\s*(\w+)\s*->\s*((?:\w+\s*)*)$)");
regex argPattern(R"(\$(\d+))");
smatch results;
 
// Read terminal patterns
string line;
while (true) {
getline(inFile, line);
 
// Terminals section ends with a blank line
if (regex_match(line, blankLine))
break;
 
regex_match(line, results, terminalPattern);
terminals[results[1]] = results[2];
}
 
outFile << "#include <iostream>" << endl;
outFile << "#include <fstream>" << endl;
outFile << "#include <string>" << endl;
outFile << "#include <regex>" << endl;
outFile << "using namespace std;" << endl << endl;
 
// Generate the token processing functions
outFile << "string input, nextToken, nextTokenValue;" << endl;
outFile << "string prevToken, prevTokenValue;" << endl << endl;
 
outFile << "void advanceToken() {" << endl;
outFile << " static smatch results;" << endl << endl;
 
outFile << " prevToken = nextToken;" << endl;
outFile << " prevTokenValue = nextTokenValue;" << endl << endl;
 
for (auto i = terminals.begin(); i != terminals.end(); ++i) {
string name = i->first + "_pattern";
string pattern = i->second;
 
outFile << " static regex " << name << "(R\"(^\\s*(" << pattern << "))\");" << endl;
outFile << " if (regex_search(input, results, " << name << ", regex_constants::match_continuous)) {" << endl;
outFile << " nextToken = \"" << i->first << "\";" << endl;
outFile << " nextTokenValue = results[1];" << endl;
outFile << " input = regex_replace(input, " << name << ", \"\");" << endl;
outFile << " return;" << endl;
outFile << " }" << endl << endl;
}
 
outFile << " static regex eof(R\"(\\s*)\");" << endl;
outFile << " if (regex_match(input, results, eof, regex_constants::match_continuous)) {" << endl;
outFile << " nextToken = \"\";" << endl;
outFile << " nextTokenValue = \"\";" << endl;
outFile << " return;" << endl;
outFile << " }" << endl << endl;
 
outFile << " throw \"Unknown token\";" << endl;
outFile << "}" << endl << endl;
 
outFile << "bool same(string symbol) {" << endl;
outFile << " if (symbol == nextToken) {" << endl;
outFile << " advanceToken();" << endl;
outFile << " return true;" << endl;
outFile << " }" << endl;
outFile << " return false;" << endl;
outFile << "}" << endl << endl;
 
// Copy the header code to the output
while (true) {
getline(inFile, line);
 
// Copy lines until we reach the first rule
if (regex_match(line, results, rulePattern))
break;
 
outFile << line << endl;
}
 
// Build the nonterminal table
while (true) {
// results already contains the last matched rule
string name = results[1];
stringstream ss(results[2]);
 
string tempString;
vector<string> tempVector;
while (ss >> tempString)
tempVector.push_back(tempString);
nonterminalRules[name].push_back(tempVector);
 
// Read code until another rule is found
string code = "";
while (true) {
getline(inFile, line);
 
if (!inFile || regex_match(line, results, rulePattern))
break;
 
// Replace $1 with results[1], etc.
line = regex_replace(line, argPattern, "results[$1]");
 
code += line + "\n";
}
nonterminalCode[name].push_back(code);
 
// Stop when we reach the end of the file
if (!inFile)
break;
}
 
// Generate the first sets, inefficiently
bool done = false;
while (!done)
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
string name = i->first;
done = true;
 
if (nonterminalFirst.find(i->first) == nonterminalFirst.end())
nonterminalFirst[i->first] = set<string>();
 
for (int j = 0; j < i->second.size(); ++j) {
if (i->second[j].size() == 0)
nonterminalFirst[i->first].insert("");
else {
string first = i->second[j][0];
if (nonterminalFirst.find(first) != nonterminalFirst.end()) {
for (auto k = nonterminalFirst[first].begin(); k != nonterminalFirst[first].end(); ++k) {
if (nonterminalFirst[name].find(*k) == nonterminalFirst[name].end()) {
nonterminalFirst[name].insert(*k);
done = false;
}
}
} else if (nonterminalFirst[name].find(first) == nonterminalFirst[name].end()) {
nonterminalFirst[name].insert(first);
done = false;
}
}
}
}
 
// Generate function signatures for the nonterminals
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
string name = i->first + "_rule";
outFile << "string " << name << "();" << endl;
}
outFile << endl;
 
// Generate the nonterminal functions
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
string name = i->first + "_rule";
outFile << "string " << name << "() {" << endl;
outFile << " vector<string> results;" << endl;
outFile << " results.push_back(\"\");" << endl << endl;
 
// Check if this rule can match an empty string
int epsilon = -1;
for (int j = 0; epsilon == -1 && j < i->second.size(); ++j)
if (i->second[j].size() == 0)
epsilon = j;
 
// Generate each production
for (int j = 0; j < i->second.size(); ++j) {
// Nothing to generate for an empty rule
if (j == epsilon)
continue;
 
string token = i->second[j][0];
if (terminals.find(token) != terminals.end())
outFile << " if (nextToken == \"" << i->second[j][0] << "\") {" << endl;
else {
outFile << " if (";
bool first = true;
for (auto k = nonterminalFirst[token].begin(); k != nonterminalFirst[token].end(); ++k, first = false) {
if (!first)
outFile << " || ";
outFile << "nextToken == \"" << (*k) << "\"";
}
outFile << ") {" << endl;
}
 
for (int k = 0; k < i->second[j].size(); ++k) {
if (terminals.find(i->second[j][k]) != terminals.end()) {
outFile << " if(same(\"" << i->second[j][k] << "\"))" << endl;
outFile << " results.push_back(prevTokenValue);" << endl;
outFile << " else" << endl;
outFile << " throw \"Syntax error - mismatched token\";" << endl;
} else
outFile << " results.push_back(" << i->second[j][k] << "_rule());" << endl;
}
 
// Copy rule code to output
outFile << nonterminalCode[i->first][j];
 
outFile << " }" << endl << endl;
}
 
if (epsilon == -1)
outFile << " throw \"Syntax error - unmatched token\";" << endl;
else
outFile << nonterminalCode[i->first][epsilon];
 
outFile << "}" << endl << endl;
}
 
// Generate the main function
outFile << "int main(int argc, char **argv) {" << endl;
outFile << " if(argc < 2) {" << endl;
outFile << " cout << \"Usage: <input file>\" << endl;" << endl;
outFile << " return 1;" << endl;
outFile << " }" << endl << endl;
 
outFile << " ifstream file(argv[1]);" << endl;
outFile << " string line;" << endl;
outFile << " input = \"\";" << endl << endl;
 
outFile << " while(true) {" << endl;
outFile << " getline(file, line);" << endl;
outFile << " if(!file) break;" << endl;
outFile << " input += line + \"\\n\";" << endl;
outFile << " }" << endl << endl;
 
outFile << " advanceToken();" << endl << endl;
 
outFile << " start_rule();" << endl;
outFile << "}" << endl;
}
 

Example grammar:

plus	\+
minus	-
times	\*
div	/
open	\(
close	\)
num	[0-9]+
var	[a-z]+

string nextLabel() {
	static string label = "0000";
	for(int i = label.length() - 1; i >= 0; --i) {
		if(label[i] == '9')
			label[i] = '0';
		else {
			++label[i];
			break;
		}
	}
	return "_" + label;
}

!! start -> expr start2
if($2 == "")
	return $1;
else {
	string label = nextLabel();
	cout << label << " = " << $1 << " " << $2 << endl;
	return label;
}

!! start2 -> plus start
return "+ " + $2;

!! start2 -> minus start
return "- " + $2;

!! start2 -> 
return "";

!! expr -> term expr2
if($2 == "")
	return $1;
else {
	string label = nextLabel();
	cout << label << " = " << $1 << " " << $2 << endl;
	return label;
}

!! expr2 -> times expr
return "* " + $2;

!! expr2 -> div expr
return "/ " + $2;

!! expr2 ->
return "";

!! term -> var
return $1;

!! term -> num
return $1;

!! term -> open start close
return $2;

Example input to parser (filename passed through command line):

(one + two) * three + four * five

Output (to standard out):

_0001 = one + two
_0002 = _0001 * three
_0003 = four * five
_0004 = _0002 + _0003

J[edit]

J's native recursive descent parser is adequate for this task, if we map names appropriately.

Implementation:

cocurrent 'base'
 
inlocale=: 4 :0 L:0
x,'_',y,'_'
)
 
parse=: 3 :0
sentence=. ;:y
opinds=. (;:'+*-')i.sentence
opfuns=. (;:'plus times minus') inlocale 'base'
scratch=. cocreate''
coinsert__scratch 'base'
names=. ~.sentence#~_1<:nc sentence
(names inlocale scratch)=: names
r=. do__scratch ;:inv opinds}((#sentence)#"0 opfuns),sentence
codestroy__scratch''
r
)
 
term=: 1 :0
2 :('m''',m,'''expr n')
)
 
expr=:1 :0
:
r=. genname''
emit r,'=:',x,m,y
r
)
 
plus=: '+' expr
times=: '*' term
minus=: '-' expr
 
N=: 10000
genname=: 3 :0
'z',}.":N=: N+1
)
 
emit=: smoutput
 

Task example:

   parse '(one + two) * three - four * five'
z0001=:four*five
z0002=:one+two
z0003=:z0002*three
z0004=:z0003-z0001
z0004

See also http://www.jsoftware.com/svn/base/trunk/packages/misc/trace.ijs for a model of the underlying parser being employed here.