fork download
copy 
  1. /*
  2.    CFGrl Version 1 -- converts .cfg-r file to equivalent .cfg file
  3.  
  4.    Author:   Adam Roegiest
  5.    Version:  1.0
  6.  
  7.    Input:  .cfg-r file with a single derivation
  8.    Output: .cfg file with abbreviated forward leftmost version of the derivation
  9.  
  10.    Literal translation of CFGrl Version 2 by Ondrej Lhotak. Available (currently) at:
  11.  
  12.      http://w...content-available-to-author-only...o.ca/~cs241/a08/CFGrl.java
  13.  
  14. */
  15.  
  16.  
  17. #include <set>
  18. #include <string>
  19. #include <iostream>
  20. #include <list>
  21. #include <sstream>
  22. #include <stack>
  23. using namespace std;
  24.  
  25. set<string> terms;
  26. set<string> nonterms;
  27. set<string> prods;
  28. string start;
  29.  
  30. struct Tree {
  31.     string rule;
  32.     list<Tree*> children;
  33.  
  34.     ~Tree() {
  35.         for(list<Tree*>::iterator it=children.begin(); it != children.end(); it++) {  // delete all subtrees
  36.             delete (*it);
  37.         }
  38.     }
  39. };
  40.  
  41. void readsyms(set<string> &t) {
  42.     int n;
  43.     string temp;
  44.     getline(cin,temp);
  45.     istringstream iss(temp);
  46.     iss >> n;
  47.     if (iss.fail()) return;
  48.     for(int i = 0; i < n; i++) {
  49.         getline(cin,temp);
  50.         t.insert(temp);
  51.     }
  52. }
  53.  
  54. void traverse(Tree *t, int d) {
  55.     for(int i = 0; i < d; i++) cout << " ";
  56.     cout << t->rule << endl; // print root
  57.     for(list<Tree*>::iterator it=(t->children).begin(); it != (t->children).end(); it++) {  // print all subtrees
  58.         traverse(*it, d+1);
  59.     }
  60. }
  61.  
  62. void dump(set<string> &h) {
  63.     cout << h.size() << endl;
  64.     for(set<string>::iterator it=h.begin(); it != h.end(); it++) {
  65.         cout << *it << endl;
  66.     }
  67. }
  68.  
  69. void popper(stack<Tree *> &myStack, list<string> &rhs, string rule) {
  70.     Tree *n = new Tree();
  71.     n->rule = rule;
  72.     for(list<string>::iterator it=rhs.begin(); it != rhs.end(); it++){
  73.         Tree *tmp = myStack.top();
  74.         n->children.push_front(tmp);
  75.         myStack.pop();
  76.     }
  77.     myStack.push(n);
  78. }
  79.  
  80. Tree* lrdo() {
  81.     stack<Tree*> myStack;
  82.     string l; // lhs symbol
  83.     do {
  84.         string f;
  85.         getline(cin,f);
  86.         list<string> r; // rhs symbols
  87.         istringstream iss(f);
  88.         iss >> l; // lhs symbol
  89.         string s;
  90.         while(iss >> s) {
  91.             if(nonterms.count(s) > 0) r.push_back(s); // only non-terminals
  92.         }
  93.         popper(myStack, r, f); // reduce rule
  94.     } while(start != l);
  95.     return myStack.top();
  96. }
  97.  
  98. int main(){
  99.     readsyms(terms); // read terminals
  100.     readsyms(nonterms); // read nonterminals
  101.     getline(cin,start); // read start symbol
  102.     readsyms(prods); // read production rules
  103.  
  104.     Tree *parsetree = lrdo(); // read reverse rightmost derivation
  105.     dump(terms); // write terminals in .cfg format
  106.     dump(nonterms); // write nonterminals
  107.     cout << start << endl; // write start symbol
  108.     dump(prods); // write production rules
  109.     traverse(parsetree, 0); // write forward leftmost derivation
  110.     delete parsetree;
  111. }
  112.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
35
AMP
BECOMES
BOF
COMMA
DELETE
ELSE
EOF
EQ
GE
GT
ID
IF
INT
LBRACE
LBRACK
LE
LPAREN
LT
MINUS
NE
NEW
NULL
NUM
PCT
PLUS
PRINTLN
RBRACE
RBRACK
RETURN
RPAREN
SEMI
SLASH
STAR
WAIN
WHILE
17
start
dcl
dcls
expr
factor
lvalue
procedure
procedures
main
params
paramlist
statement
statements
term
test
type
arglist
start
49
start BOF procedures EOF
procedures procedure procedures
procedures main
procedure INT ID LPAREN params RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
main INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
params
params paramlist
paramlist dcl
paramlist dcl COMMA paramlist
type INT
type INT STAR
dcls
dcls dcls dcl BECOMES NUM SEMI
dcls dcls dcl BECOMES NULL SEMI
dcl type ID
statements
statements statements statement
statement lvalue BECOMES expr SEMI
statement IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
statement WHILE LPAREN test RPAREN LBRACE statements RBRACE
statement PRINTLN LPAREN expr RPAREN SEMI
statement DELETE LBRACK RBRACK expr SEMI
test expr EQ expr
test expr NE expr
test expr LT expr
test expr LE expr
test expr GE expr
test expr GT expr
expr term
expr expr PLUS term
expr expr MINUS term
term factor
term term STAR factor
term term SLASH factor
term term PCT factor
factor ID
factor NUM
factor NULL  
factor LPAREN expr RPAREN
factor AMP lvalue
factor STAR factor
factor NEW INT LBRACK expr RBRACK
factor ID LPAREN RPAREN
factor ID LPAREN arglist RPAREN
arglist expr
arglist expr COMMA arglist
lvalue ID
lvalue STAR factor
lvalue LPAREN lvalue RPAREN
type INT
dcl type ID
type INT
dcl type ID
dcls
statements
factor ID
term factor
expr term
factor ID
term factor
factor ID
term term STAR factor
expr expr PLUS term
main INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
procedures main
start BOF procedures EOF
stdout
copy 
35
AMP
BECOMES
BOF
COMMA
DELETE
ELSE
EOF
EQ
GE
GT
ID
IF
INT
LBRACE
LBRACK
LE
LPAREN
LT
MINUS
NE
NEW
NULL
NUM
PCT
PLUS
PRINTLN
RBRACE
RBRACK
RETURN
RPAREN
SEMI
SLASH
STAR
WAIN
WHILE
17
arglist
dcl
dcls
expr
factor
lvalue
main
paramlist
params
procedure
procedures
start
statement
statements
term
test
type
start
49
arglist expr
arglist expr COMMA arglist
dcl type ID
dcls
dcls dcls dcl BECOMES NULL SEMI
dcls dcls dcl BECOMES NUM SEMI
expr expr MINUS term
expr expr PLUS term
expr term
factor AMP lvalue
factor ID
factor ID LPAREN RPAREN
factor ID LPAREN arglist RPAREN
factor LPAREN expr RPAREN
factor NEW INT LBRACK expr RBRACK
factor NULL  
factor NUM
factor STAR factor
lvalue ID
lvalue LPAREN lvalue RPAREN
lvalue STAR factor
main INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
paramlist dcl
paramlist dcl COMMA paramlist
params
params paramlist
procedure INT ID LPAREN params RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
procedures main
procedures procedure procedures
start BOF procedures EOF
statement DELETE LBRACK RBRACK expr SEMI
statement IF LPAREN test RPAREN LBRACE statements RBRACE ELSE LBRACE statements RBRACE
statement PRINTLN LPAREN expr RPAREN SEMI
statement WHILE LPAREN test RPAREN LBRACE statements RBRACE
statement lvalue BECOMES expr SEMI
statements
statements statements statement
term factor
term term PCT factor
term term SLASH factor
term term STAR factor
test expr EQ expr
test expr GE expr
test expr GT expr
test expr LE expr
test expr LT expr
test expr NE expr
type INT
type INT STAR
start BOF procedures EOF
 procedures main
  main INT WAIN LPAREN dcl COMMA dcl RPAREN LBRACE dcls statements RETURN expr SEMI RBRACE
   dcl type ID
    type INT
   dcl type ID
    type INT
   dcls
   statements
   expr expr PLUS term
    expr term
     term factor
      factor ID
    term term STAR factor
     term factor
      factor ID
     factor ID
https://ideone.com/nnJrT1
language:
C++ (gcc 8.3)
created:
39 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!