Rosetta Code

Recursive descent parser generator: Difference between revisions

Page Discussion

Recursive descent parser generator (view source)

Revision as of 10:53, 2 February 2024

32,511 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(6 intermediate revisions by 6 users not shown)
Line 24:
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.
 
<langsyntaxhighlight lang="cpp">
#include <iostream>
#include <fstream>
#include <stringiostream>
#include <sstream>
#include <map>
#include <regex>
#include <set>
#include <regexsstream>
#include <string>
using namespace std;
 
Line 40:
 
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;
<< endl;
 
// Generate the token processing functions
outFile << "string input, nextToken, nextTokenValue;" << endl;
outFile << "string prevToken, prevTokenValue;" << endl << endl;
<< endl
<< "void advanceToken() {" << endl
<< " static smatch results;" << endl
<< endl
<< " prevToken = nextToken;" << endl
<< " prevTokenValue = nextTokenValue;" << endl
<< endl;
 
for (auto i = terminals.begin(); i != terminals.end(); ++i) {
outFile << "void advanceToken() {" << endl;
string name = i->first + "_pattern";
outFile << " static smatch results;" << endl << endl;
string pattern = i->second;
 
outFile << " prevTokenstatic =regex nextToken" << name << "(R\"(^\\s*(" << pattern << "))\");" << endl;
<< " if (regex_search(input, results, " << name << ", regex_constants::match_continuous)) {" << endl
outFile << " prevTokenValue = nextTokenValue;" << endl << endl;
<< " nextToken = \"" << i->first << "\";" << endl
<< " nextTokenValue = results[1];" << endl
<< " input = regex_replace(input, " << name << ", \"\");" << endl
<< " return;" << endl
<< " }" << endl
<< endl;
}
 
outFile << " static regex eof(R\"(\\s*)\");" << endl
for (auto i = terminals.begin(); i != terminals.end(); ++i) {
<< " if (regex_match(input, results, eof, regex_constants::match_continuous)) {" << endl
string name = i->first + "_pattern";
<< " nextToken = \"\";" << endl
string pattern = i->second;
<< " nextTokenValue = \"\";" << endl
<< " return;" << endl
<< " }" << endl
<< endl
<< " throw \"Unknown token\";" << endl
<< "}" << endl
<< endl
<< "bool same(string symbol) {" << endl
<< " if (symbol == nextToken) {" << endl
<< " advanceToken();" << endl
<< " return true;" << endl
<< " }" << endl
<< " return false;" << endl
<< "}" << endl
<< endl;
 
// Copy the header code to the output
outFile << " static regex " << name << "(R\"(^\\s*(" << pattern << "))\");" << endl;
while (true) {
outFile << " if (regex_search(input, results, " << name << ", regex_constants::match_continuous)) {" << endl;
getline(inFile, line);
outFile << " nextToken = \"" << i->first << "\";" << endl;
outFile << " nextTokenValue = results[1];" << endl;
outFile << " input = regex_replace(input, " << name << ", \"\");" << endl;
outFile << " return;" << endl;
outFile << " }" << endl << endl;
}
 
// Copy lines until we reach the first rule
outFile << " static regex eof(R\"(\\s*)\");" << endl;
outFile << " if (regex_match(inputline, results, eof, regex_constants::match_continuousrulePattern)) {" << endl;
break;
outFile << " nextToken = \"\";" << endl;
outFile << " nextTokenValue = \"\";" << endl;
outFile << " return;" << endl;
outFile << " }" << endl << endl;
 
outFile << " throw \"Unknown token\";"line << endl;
}
outFile << "}" << endl << endl;
 
// Build the nonterminal table
outFile << "bool same(string symbol) {" << endl;
while (true) {
outFile << " if (symbol == nextToken) {" << endl;
// results already contains the last matched rule
outFile << " advanceToken();" << endl;
string name = results[1];
outFile << " return true;" << endl;
stringstream ss(results[2]);
outFile << " }" << endl;
outFile << " return false;" << endl;
outFile << "}" << endl << endl;
 
string tempString;
// Copy the header code to the output
vector<string> tempVector;
while (true) {
while (ss >> tempString)
getline(inFile, line);
tempVector.push_back(tempString);
nonterminalRules[name].push_back(tempVector);
// Copy lines until we reach the first rule
if (regex_match(line, results, rulePattern))
break;
 
// Read code until another rule is found
outFile << line << endl;
string code = "";
}
while (true) {
getline(inFile, line);
 
if (!inFile || regex_match(line, results, rulePattern))
// Build the nonterminal table
break;
while (true) {
// results already contains the last matched rule
string name = results[1];
stringstream ss(results[2]);
 
// Replace $1 with results[1], etc.
string tempString;
line = regex_replace(line, argPattern, "results[$1]");
vector<string> tempVector;
while (ss >> tempString)
tempVector.push_back(tempString);
nonterminalRules[name].push_back(tempVector);
 
code += line + "\n";
// Read code until another rule is found
}
string code = "";
nonterminalCode[name].push_back(code);
while (true) {
getline(inFile, line);
 
// Stop when we reach the end of the file
if (!inFile || regex_match(line, results, rulePattern))
if (!inFile)
break;
break;
}
 
// Generate the first sets, inefficiently
// Replace $1 with results[1], etc.
bool done = false;
line = regex_replace(line, argPattern, "results[$1]");
while (!done)
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
string name = i->first;
done = true;
 
if (nonterminalFirst.find(i->first) == nonterminalFirst.end())
code += line + "\n";
nonterminalFirst[i->first] = set<string>();
}
nonterminalCode[name].push_back(code);
 
for (int j = 0; j < i->second.size(); ++j) {
// Stop when we reach the end of the file
if (i->second[j].size() == 0)
if (!inFile)
nonterminalFirst[i->first].insert("");
break;
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 thefunction firstsignatures sets,for the inefficientlynonterminals
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
bool done = false;
string name = i->first + "_rule";
while (!done)
outFile << "string " << name << "();" << endl;
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
}
string name = i->first;
outFile << endl;
done = true;
 
// Generate the nonterminal functions
if (nonterminalFirst.find(i->first) == nonterminalFirst.end())
for (auto i = nonterminalRules.begin(); i != nonterminalRules.end(); ++i) {
nonterminalFirst[i->first] = set<string>();
string name = i->first + "_rule";
outFile << "string " << name << "() {" << endl
<< " vector<string> results;" << endl
<< " results.push_back(\"\");" << endl
<< endl;
 
// Check if this rule can match an empty string
for (int j = 0; j < i->second.size(); ++j) {
int epsilon = -1;
if (i->second[j].size() == 0)
for (int j = 0; epsilon == -1 && j < i->second.size(); ++j)
nonterminalFirst[i->first].insert("");
if (i->second[j].size() == 0)
else {
epsilon = j;
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 each production
// Generate function signatures for the nonterminals
for (autoint ij = nonterminalRules.begin()0; ij !=< nonterminalRulesi->second.endsize(); ++ij) {
// Nothing to generate for an empty rule
string name = i->first + "_rule";
if (j == epsilon)
outFile << "string " << name << "();" << endl;
continue;
}
outFile << endl;
 
string token = i->second[j][0];
// Generate the nonterminal functions
for (auto i = nonterminalRules if (terminals.beginfind(token); i != nonterminalRulesterminals.end(); ++i) {
outFile << " if (nextToken == \"" << i->second[j][0] << "\") {" << endl;
string name = i->first + "_rule";
else {
outFile << "string " << name << "() {" << endl;
outFile << " vector<string>if results;(" << endl;
bool first = true;
outFile << " results.push_back(\"\");" << endl << endl;
for (auto k = nonterminalFirst[token].begin(); k != nonterminalFirst[token].end(); ++k, first = false) {
if (!first)
// Check if this rule can match an empty string
outFile << " || ";
int epsilon = -1;
outFile << "nextToken == \"" << (*k) << "\"";
for (int j = 0; epsilon == -1 && j < i->second.size(); ++j)
}
if (i->second[j].size() == 0)
outFile << ") {" << endl;
epsilon = j;
}
 
for (int k = 0; k < i->second[j].size(); ++k) {
// Generate each production
for (int j = 0; j < if (terminals.find(i->second[j][k]) != terminals.sizeend(); ++j) {
outFile << " if(same(\"" << i->second[j][k] << "\"))" << endl
// Nothing to generate for an empty rule
<< " results.push_back(prevTokenValue);" << endl
if (j == epsilon)
<< " else" << endl
continue;
<< " throw \"Syntax error - mismatched token\";" << endl;
} else
outFile << " results.push_back(" << i->second[j][k] << "_rule());" << endl;
}
 
// Copy rule code to output
string token = i->second[j][0];
outFile << nonterminalCode[i->first][j];
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;
}
 
outFile << " }" << endl << endl;
// Copy rule code to output
}
outFile << nonterminalCode[i->first][j];
 
if (epsilon == -1)
outFile << " }" << endl << endl;
outFile << " throw \"Syntax error - unmatched token\";" << endl;
}
else
 
outFile << nonterminalCode[i->first][epsilon];
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;
}
 
// Generate the main function
outFile << " start_rule();" << endl;
outFile << "}int main(int argc, char **argv) {" << endl;
<< " if(argc < 2) {" << endl
<< " cout << \"Usage: <input file>\" << endl;" << endl
<< " return 1;" << endl
<< " }" << endl
<< endl
<< " ifstream file(argv[1]);" << endl
<< " string line;" << endl
<< " input = \"\";" << endl
<< endl
<< " while(true) {" << endl
<< " getline(file, line);" << endl
<< " if(!file) break;" << endl
<< " input += line + \"\\n\";" << endl
<< " }" << endl
<< endl
<< " advanceToken();" << endl
<< endl
<< " start_rule();" << endl
<< "}" << endl;
}
</syntaxhighlight>
</lang>
 
Example grammar:
Line 362 ⟶ 367:
 
I've therefore applied this parser to the expression designated by the task, which only involves binary expressions and identifiers, and written a separate routine to convert the resulting AST into three-address code.
<langsyntaxhighlight lang="go">package main
 
import (
Line 466 ⟶ 471:
last = i
}
}</langsyntaxhighlight>
 
{{out}}
Line 535 ⟶ 540:
Implementation:
 
<langsyntaxhighlight Jlang="j">cocurrent 'base'
 
inlocale=: 4 :0 L:0
Line 575 ⟶ 580:
 
emit=: smoutput
</syntaxhighlight>
</lang>
 
Task example:
 
<langsyntaxhighlight Jlang="j"> parse '(one + two) * three - four * five'
z0001=:four*five
z0002=:one+two
z0003=:z0002*three
z0004=:z0003-z0001
z0004</langsyntaxhighlight>
 
See also https://github.com/jsoftware/general_misc/blob/master/trace.ijs for a model of the underlying parser being employed here.
Line 590 ⟶ 595:
=={{header|Julia}}==
The Julia compiler's own parser is a recursive descent parser, and can be used directly here.
<langsyntaxhighlight lang="julia">const one, two, three, four, five, six, seven, eight, nine = collect(1:9)
 
function testparser(s)
Line 598 ⟶ 603:
 
testparser("(one + two) * three - four * five")
</langsyntaxhighlight>{{out}}
<pre>
$(Expr(:thunk, CodeInfo(
Line 610 ⟶ 615:
</pre>
 
=={{header|PhixPerl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
Technically the task is asking for code which generates something like the following, so I suppose
it would actually meet the spec if it began with <code>constant src = """</code> and ended with
<code>""" puts(1,src)</code>...
<lang Phix>string src
integer ch, sdx
sequence tok
procedure skip_spaces()
while 1 do
if sdx>length(src) then exit end if
ch = src[sdx]
if not find(ch," \t\r\n") then exit end if
sdx += 1
end while
end procedure
procedure next_token()
-- yeilds one of:
-- {"SYMBOL",ch} where ch is one of "()+-/*", or
-- {"IDENT",string}, or {"EOF"}
skip_spaces()
integer tokstart = sdx
if sdx>length(src) then
tok = {"EOF"}
elsif find(ch,"()+-/*") then
sdx += 1
tok = {"SYMBOL",ch&""}
elsif (ch>='a' and ch<='z')
or (ch>='A' and ch<='Z') then
while true do
sdx += 1
if sdx>length(src) then exit end if
ch = src[sdx]
if ch!='_'
and (ch<'a' or ch>'z')
and (ch<'A' or ch>'Z')
and (ch<'0' or ch>'9') then
exit
end if
end while
tok = {"IDENT",src[tokstart..sdx-1]}
else
?9/0
end if
end procedure
 
use strict; # https://rosettacode.org/wiki/Recursive_descent_parser_generator
forward function sum_expr()
use warnings;
use Path::Tiny;
 
my $h = qr/\G\s*/;
function primary()
my $identifier = qr/$h([a-z]\w*)\b/i;
sequence res
my $literal = qr/$h(['"])(.+?)\1/s;
if tok[1]="IDENT" then
my (%rules, %called, $usercode, %patches);
res = tok
my $filename = './generatedparser.pl';
next_token()
elsif tok={"SYMBOL","("} then
next_token()
res = sum_expr()
if tok!={"SYMBOL",")"} then ?9/0 end if
next_token()
else
?9/0
end if
return res
end function
 
sub node { bless [ @_[1..$#_] ], $_[0] }
function mul_expr()
sub error { die "ERROR: ", s/\G\s*\K/<**ERROR @_**>/r, "\n" }
sequence res = primary()
sub want { /$h\Q$_[1]\E/gc ? shift : error "missing '$_[1]' " }
while true do
sub addin { node $_[0] => ref $_[1] eq $_[0] ? @{$_[1]} : $_[1], pop }
if tok[1]!="SYMBOL" or not find(tok[2],{"*","/"}) then exit end if
res = {tok,res,NULL}
next_token()
res[3] = primary()
end while
return res
end function
 
local $_ = do { local $/; @ARGV ? <> : <DATA> }; # the EBNF
function sum_expr()
$usercode = s/^(#usercode.*)//ms ? $1 : "# no usercode included\n";;
sequence res = mul_expr()
$patches{PATCHUSER} = $usercode . "#end usercode\n"; # grammar support code
while true do
s/^\h*#.*\n//gm; # remove comment lines
if tok[1]!="SYMBOL" or not find(tok[2],{"+","-"}) then exit end if
$patches{PATCHGRAMMAR} = s/^(?:\h*\n)+//r =~ s/\n(?:\h*\n)+\z//r;
res = {tok,res,NULL}
while( /$identifier\s*=/gc ) # the start of a rule
next_token()
{
res[3] = mul_expr()
my $name end= while$1;
$rules{startsymbol} //= node RULE => $name;
return res
my $tree = expr(0);
end function
$rules{$name} = $rules{$name} ? addin ALT => $rules{$name}, $tree : $tree;
/$h[.;]/gc or error 'missing rule terminator, needs . or ;';
}
/\G\s*\z/ or error "incomplete parse at ", substr $_, pos($_) // 0;
%rules or error "no rules found ";
delete @called{keys %rules};
%called and die "\nERROR: undefined rule(s) <@{[ keys %called]}>\n";
 
sub expr # precedence climbing parser for grammer rules
integer nxt = 1
{
function show_ast(sequence ast)
my $tree =
if ast[1][1]="SYMBOL" then
/$h(NAME)\b/gc ? node $1 : # internal name matcher
string op = ast[1][2],
/$identifier/gc ? do { $called{$1}++; node RULE => $1 } :
lhs = show_ast(ast[2]),
/$literal/gc ? node LIT => $2 rhs = show_ast(ast[3]),:
/$h<(\w+)>/gc ? node ACTION => $1 :
this = sprintf("_%04d",nxt)
/$h\[/gc ? node OPTION => want expr(0), ']' :
printf(1,"%s = %s %s %s\n",{this,lhs,op,rhs})
/$h\{/gc ? node REPEAT => want expr(0), '}' :
nxt += 1
/$h\(/gc ? want expr(0), ')' :
return this
error 'Invalid expression';
elsif ast[1]="IDENT" then
$tree =
return ast[2]
/\G\s+/gc ? $tree :
end if
$_[0] <= 1 && /\G(?=[[<{('"a-z])/gci ? addin SEQ => $tree, expr(2) :
?9/0
$_[0] <= 0 && /\G\|/gc ? addin ALT => $tree, expr(1) :
end function
return $tree while 1;
}
 
my $perlcode = "# generated code (put in Rule:: package)\n";
procedure parse(string source)
for my $rule ( sort keys %rules )
src = source
{
sdx = 1
my $body = $rules{$rule}->code;
next_token()
$perlcode .= "\nsub Rule::$rule\n\t{\n\t$body\n\t}\n";
sequence ast = sum_expr()
}
if tok!={"EOF"} then ?9/0 end if
$perlcode =~ s/^(?:\h*\n)+(?=\h*\})//gm;
pp(ast,{pp_Nest,4})
$perlcode .= "\n# preceding code was generated for rules\n";
{} = show_ast(ast)
$patches{PATCHGENERATED} = $perlcode;
end procedure
sub ALT::code
{
my $all = join " or\n\t", map $_->code, @{ $_[0] };
"( # alt\n\t$all )"
}
sub SEQ::code
{
my $all = join " and\n\t", map $_->code, @{ $_[0] };
"( # seq\n\t$all )"
}
sub REPEAT::code { "do { # repeat\n\t1 while @{[ $_[0][0]->code ]} ; 1 }" }
sub OPTION::code { "( # option\n\t@{[ $_[0][0]->code ]} or 1 )" }
sub RULE::code { "Rule::$_[0][0]()" }
sub ACTION::code { "( $_[0][0]() || 1 )" }
sub NAME::code { "( /\\G\$whitespace(\\w+)/gc and push \@stack, \$1 )" }
sub LIT::code { "( /\\G\$whitespace(\Q$_[0][0]\E)/gc and push \@stack, \$1 )" }
 
$_ = <<'END'; ##################################### template for generated code
parse("(one + two) * three - four * five")</lang>
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Recursive_descent_parser_generator
use warnings; # WARNING: this code is generated
 
my @stack;
my $whitespace = qr/\s*/;
 
my $grammar = <<'GRAMMAR'; # make grammar rules available to usercode
PATCHGRAMMAR
GRAMMAR
 
PATCHUSER
PATCHGENERATED
local $_ = shift // '(one + two) * three - four * five';
eval { begin() }; # eval because it is optional
Rule::startsymbol();
eval { end() }; # eval because it is optional
/\G\s*\z/ or die "ERROR: incomplete parse\n";
END
 
s/(PATCH\w+)/$patches{$1}/g; # insert grammar variable stuff
path( $filename )->spew( $_ );
chmod 0555, $filename; # readonly, executable
exec 'perl', $filename, @ARGV or die "exec failed $!";
 
__DATA__
 
expr = term { plus term <gen3addr> } .
term = factor { times factor <gen3addr> } .
factor = primary [ '^' factor <gen3addr> ] .
primary = '(' expr ')' <removeparens> | NAME .
plus = "+" | "-" .
times = "*" | "/" .
 
#usercode -- separator for included code for actions
 
my $temp = '0000';
 
sub begin { print "parsing: $_\n\n" }
 
sub gen3addr
{
@stack >= 3 or die "not enough on stack";
my @three = splice @stack, -3, 3, my $t = '_' . ++$temp;
print "$t = @three\n";
}
 
sub removeparens
{
@stack >= 3 or die "not enough on stack";
splice @stack, -3, 3, $stack[-2];
}</syntaxhighlight>
Running the above with no arguments uses a default grammar that will solve the specified example. It produces
the following perl script (and then runs it).
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Recursive_descent_parser_generator
use warnings; # WARNING: this code is generated
 
my @stack;
my $whitespace = qr/\s*/;
 
my $grammar = <<'GRAMMAR'; # make grammar rules available to usercode
expr = term { plus term <gen3addr> } .
term = factor { times factor <gen3addr> } .
factor = primary [ '^' factor <gen3addr> ] .
primary = '(' expr ')' <removeparens> | NAME .
plus = "+" | "-" .
times = "*" | "/" .
GRAMMAR
 
#usercode -- separator for included code for actions
 
my $temp = '0000';
 
sub begin { print "parsing: $_\n\n" }
 
sub gen3addr
{
@stack >= 3 or die "not enough on stack";
my @three = splice @stack, -3, 3, my $t = '_' . ++$temp;
print "$t = @three\n";
}
 
sub removeparens
{
@stack >= 3 or die "not enough on stack";
splice @stack, -3, 3, $stack[-2];
}
#end usercode
 
# generated code (put in Rule:: package)
 
sub Rule::expr
{
( # seq
Rule::term() and
do { # repeat
1 while ( # seq
Rule::plus() and
Rule::term() and
( gen3addr() || 1 ) ) ; 1 } )
}
 
sub Rule::factor
{
( # seq
Rule::primary() and
( # option
( # seq
( /\G$whitespace(\^)/gc and push @stack, $1 ) and
Rule::factor() and
( gen3addr() || 1 ) ) or 1 ) )
}
 
sub Rule::plus
{
( # alt
( /\G$whitespace(\+)/gc and push @stack, $1 ) or
( /\G$whitespace(\-)/gc and push @stack, $1 ) )
}
 
sub Rule::primary
{
( # alt
( # seq
( /\G$whitespace(\()/gc and push @stack, $1 ) and
Rule::expr() and
( /\G$whitespace(\))/gc and push @stack, $1 ) and
( removeparens() || 1 ) ) or
( /\G$whitespace(\w+)/gc and push @stack, $1 ) )
}
 
sub Rule::startsymbol
{
Rule::expr()
}
 
sub Rule::term
{
( # seq
Rule::factor() and
do { # repeat
1 while ( # seq
Rule::times() and
Rule::factor() and
( gen3addr() || 1 ) ) ; 1 } )
}
 
sub Rule::times
{
( # alt
( /\G$whitespace(\*)/gc and push @stack, $1 ) or
( /\G$whitespace(\/)/gc and push @stack, $1 ) )
}
 
# preceding code was generated for rules
 
local $_ = shift // '(one + two) * three - four * five';
eval { begin() }; # eval because it is optional
Rule::startsymbol();
eval { end() }; # eval because it is optional
/\G\s*\z/ or die "ERROR: incomplete parse\n";</syntaxhighlight>
The above script can also be run stand-alone and produces the following output.
{{out}}
<pre>
parsing: (one + two) * three - four * five
 
_0001 = one + two
_0002 = _0001 * three
_0003 = four * five
_0004 = _0002 - _0003
</pre>
Different grammars and input can be specified on the command line.
<pre>
recursivedescentparsergenerator.pl arithexpr.y '2 * 3 + 4 * 5'
</pre>
and giving this file as "arithexpr.y"
<syntaxhighlight lang="perl"># test arith expr
 
expr = term { '+' term <fadd> | '-' term <fsub> } .
term = factor { '*' factor <fmul> | '/' factor <fdiv> } .
factor = '(' expr ')' <noparen> | NAME .
 
#usercode
 
sub noparen { splice @stack, -3, 3, $stack[-2]; }
sub fadd { splice @stack, -3, 3, $stack[-3] + $stack[-1] }
sub fsub { splice @stack, -3, 3, $stack[-3] - $stack[-1] }
sub fmul { splice @stack, -3, 3, $stack[-3] * $stack[-1] }
sub fdiv { splice @stack, -3, 3, $stack[-3] / $stack[-1] }
sub begin { print "expr = $_\n" }
sub end { print "answer = @{[pop @stack]}\n" }</syntaxhighlight>
will produce the following
{{out}}
<pre>
expr = 2 * 3 + 4 * 5
answer = 26
</pre>
 
 
 
=={{header|Phix}}==
Technically the task is asking for code which generates something like the following, so I suppose
it would actually meet the spec if it began with <code>constant src = """</code> and ended with
<code>""" puts(1,src)</code>... (and like several/most other entries on this page, this does not use a formal grammer)
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">--
-- demo\rosetta\RecursiveDescentParser.exw
-- =======================================
--</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">src</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sdx</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tok</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">skip_spaces</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\t'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\r'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- yeilds one of:
-- {"SYMBOL",ch} where ch is one of "()+-/*", or
-- {"IDENT",string}, or {"EOF"}</span>
<span style="color: #000000;">skip_spaces</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tokstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sdx</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">tok</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"EOF"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"()+-/*"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">tok</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"SYMBOL"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">&</span><span style="color: #008000;">""</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">>=</span><span style="color: #008000;">'a'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'z'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">>=</span><span style="color: #008000;">'A'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'Z'</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'_'</span>
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #008000;">'a'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'z'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #008000;">'A'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'Z'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">tok</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"IDENT"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tokstart</span><span style="color: #0000FF;">..</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">forward</span> <span style="color: #008080;">function</span> <span style="color: #000000;">sum_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">primary</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tok</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">"IDENT"</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tok</span>
<span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">tok</span><span style="color: #0000FF;">={</span><span style="color: #008000;">"SYMBOL"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"("</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sum_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tok</span><span style="color: #0000FF;">!={</span><span style="color: #008000;">"SYMBOL"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">")"</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">mul_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primary</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tok</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">"SYMBOL"</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tok</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],{</span><span style="color: #008000;">"*"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"/"</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tok</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primary</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">sum_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mul_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tok</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">"SYMBOL"</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tok</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],{</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">tok</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">}</span>
<span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mul_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nxt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">show_ast</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">ast</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ast</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">"SYMBOL"</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ast</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">lhs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">show_ast</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ast</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">rhs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">show_ast</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ast</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">nid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"_%04d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nxt</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s = %s %s %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">nid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">nxt</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nid</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ast</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">"IDENT"</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">ast</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">parse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">source</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">source</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">next_token</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ast</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sum_expr</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">tok</span><span style="color: #0000FF;">!={</span><span style="color: #008000;">"EOF"</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ast</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">show_ast</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ast</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">parse</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(one + two) * three - four * five"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 754 ⟶ 1,049:
Instead of writing a full-blown generator, it is possible to solve the task partly by making use of the built-in optimizer and study the relevant AST output
<pre>
perl6raku --target=optimize -e 'no strict; say ($one + $two) * $three - $four * $five' | tail -11
- QAST::Op(callstatic &say) <sunk> :statement_id<2> say ($one + $two) * $three - $four * $five
- QAST::Op(callstatic &infix:<->) <wanted> -
Line 770 ⟶ 1,065:
<pre>
one two + three * four five * -
</pre>
 
=={{header|Wren}}==
{{trans|Phix}}
{{libheader|Wren-str}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./str" for Char
import "./fmt" for Fmt
 
class RDP {
construct parse(source) {
_src = source
_sdx = 0
_ch = null
_tok = null
_nxt = 1
nextToken()
var ast = sumExpr()
if (_tok[0] != "EOF") Fiber.abort("Something went wrong.")
printAst(ast, 0)
System.print()
showAst(ast)
}
 
skipSpaces() {
while (true) {
if (_sdx >= _src.count) return
_ch = _src[_sdx]
if (!" \t\r\n".contains(_ch)) return
_sdx = _sdx + 1
}
}
 
// yields one of:
// ["SYMBOL", ch] where ch is one of "()+-/*", or
// ["IDENT", string] or ["EOF"]
nextToken() {
skipSpaces()
var tokStart = _sdx
if (_sdx >= _src.count) {
_tok = ["EOF"]
} else if ("()+-/*".contains(_ch)) {
_sdx = _sdx + 1
_tok = ["SYMBOL", _ch]
} else if (Char.isAsciiLetter(_ch)) {
while (true) {
_sdx = _sdx + 1
if (_sdx >= _src.count) break
_ch = _src[_sdx]
if (!Char.isAsciiAlphaNum(_ch) && _ch != "_") break
}
_tok = ["IDENT", _src[tokStart..._sdx]]
} else {
Fiber.abort("Invalid token '%(_ch)'.")
}
}
 
primary() {
var res = []
if (_tok[0] == "IDENT") {
res = _tok.toList
nextToken()
} else if (_tok[0] == "SYMBOL" && _tok[1] == "(") {
nextToken()
res = sumExpr()
if (_tok[0] != "SYMBOL" || _tok[1] != ")") Fiber.abort("Unexpected token '%(_tok)'.")
nextToken()
} else {
Fiber.abort("Unexpected token '%(_tok)'.")
}
return res
}
 
mulExpr() {
var res = primary()
while (true) {
if (_tok[0] != "SYMBOL" || !"*/".contains(_tok[1])) break
res = [_tok, res, null]
nextToken()
res[2] = primary()
}
return res
}
 
sumExpr() {
var res = mulExpr()
while (true) {
if (_tok[0] != "SYMBOL" || !"+-".contains(_tok[1])) break
res = [_tok, res, null]
nextToken()
res[2] = mulExpr()
}
return res
}
 
showAst(ast) {
if (ast[0][0] == "SYMBOL") {
var op = ast[0][1]
var lhs = showAst(ast[1])
var rhs = showAst(ast[2])
var thiz = Fmt.swrite("_$04d", _nxt)
Fmt.print("$s = $s $s $s", thiz, lhs, op, rhs)
_nxt = _nxt + 1
return thiz
} else if (ast[0] == "IDENT") {
return ast[1]
}
Fiber.abort("Something went wrong.")
}
 
printAst(ast, level) {
for (e in ast) {
var indent = " " * level
if (!(e is List)) {
System.print(indent + e)
} else {
System.print(indent + "{")
printAst(e, level+1)
System.print(indent + "}")
}
}
}
}
 
RDP.parse("(one + two) * three - four * five")</syntaxhighlight>
 
{{out}}
<pre>
{
SYMBOL
-
}
{
{
SYMBOL
*
}
{
{
SYMBOL
+
}
{
IDENT
one
}
{
IDENT
two
}
}
{
IDENT
three
}
}
{
{
SYMBOL
*
}
{
IDENT
four
}
{
IDENT
five
}
}
 
_0001 = one + two
_0002 = _0001 * three
_0003 = four * five
_0004 = _0002 - _0003
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245470...352429"