{
/*
 ast.syn -- Create an Abstract Syntax Tree

 Copyright (c) 2002 Parsifal Software. All Rights Reserved.

 The grammar contained in this file describes the same language as the
 grammar in cll.syn. Reduction procedures have been added to enable it
 to create an abstract syntax tree as it parses. Other than the addition of
 reduction procedures, there are no changes to the syntax.

 .syn files are compiled with the AnaGram parser generator, which creates a
 corresponding parser file and header file.

 To build a demonstration program that illustrates the use of this parser in
 an interpreter that executes from an abstract syntax tree, compile and link
 as a single single project:
   astxi.cpp               // Execution module
   demo.cpp                // Demo program
   ast.cpp                 // This parser, creates abstract syntax tree
   astdefs.cpp             // Node definitions
   comdefs.cpp             // Common script definitions
   agclib1\src\ag*.cpp     // Supporting class library
 Include files describing the class library are in agclib1\include

 To build a demonstration program that illustrates the use of this parser in
 an interpreter that compiles bytecode from an abstract syntax tree, compile
 and link as a single single project:
   astci.cpp               // Execution module
   demo.cpp                // Demo program
   ast.cpp                 // This parser, creates abstract syntax tree
   astdefs.cpp             // Node definitions
   bcidefs.cpp             // Bytecode and compiler definitions
   comdefs.cpp             // Common script definitions
   agclib1\src\ag*.cpp     // Supporting class library
 Include files describing the class library are in agclib1\include

 This parser analyzes a language that is similar to C.

 The language consists of C statements (not including declarations or the
 switch statement) and C expressions (not including pointers or subscript
 operators). The language also implements Fortran-style exponentiation and
 simple dump and print statements. The syntax below uses "open" and "closed"
 statements to eliminate the traditional "dangling else" or "if-else"
 ambiguity problem. See http://www.parsifalsoft.com/ifelse.html or
 doc/ifelse.htm for a more detailed discussion.

 Statement types supported are:
   expression statements
   compound statements
   if/else statements
   while statements
   do/while statements
   for statements
   break and continue statements
   dump and print statements

 There are no declarations. Scalar values may be explicitly cast to (long) or
 (double). Both integer and floating point values are stored as doubles.

 Scripts may contain any number of statements. White space may be used
 freely, including both C and C++ style comments.

 For further information about this program or the AnaGram
 parser generator, please contact:
   Parsifal Software
   http://www.parsifalsoft.com
   info@parsifalsoft.com
   +1-800-879-2577, Voice/Fax +1-508-358-2564
   P.O. Box 219
   Wayland, Massachusetts 01778
   USA
*/

#include "comdefs.h"
#include <math.h>
#include "astdefs.h"         // Defines node structure of abstract syntax tree

// Forward reference for parxer control block
struct parse_pcb_struct;

struct Tree : public AbstractSyntaxTree {
  parse_pcb_struct *pcbPointer;
  FileLocation context() const;
};

#define AST PCB.ast
}

/*** CONFIGURATION SECTION **************************************************/
[
  // Grammar adjustments
  disregard white space               // Skip over white space (defined below)
  distinguish lexemes
  lexeme {integer, real, name, string element, character constant}

  distinguish keywords {'a-z' + 'A-Z'}

  wrapper {AgString, Value}                // Special handling on parser stack
  wrapper {AgStack<AstNode *>}

  parser name = parse                                  // name parser function

  parser file name = "#.cpp"      // # will be replaced by name of syntax file
  test file mask = "*.scf"                            // filter for File Trace
  no cr        //omit carriage returns in output files, for *nix compatibility

  default token type = AstNode *

  // Operating modes
  pointer input                             // Take input from array in memory
  pointer type = const unsigned char *
  reentrant parser                                    // Make parser reentrant
  context type = FileLocation

  // Put the following into the parser control block for use during parsing
  extend pcb {
    // Declare an abstract syntax tree
    Tree ast;

    int loopDepth;
    // Constructor for pcb
    parse_pcb_struct(const char *text);

    // Functions used during parsing
    void checkLoop();
    void reportError();
  }
]

/*** GRAMMAR ****************************************************************/

/*
 "script" is marked with a $ to indicate it is the "grammar token", that is,
 the whole of the input we're intending to parse.
*/
(void) script $
 -> statement list:sl, eof =
       AST.root = AST.node(typeScript, AST.listNode(typeStatementBlock, sl));

// Zero or more statements. Note that "statement list" is recursively defined.
(AgStack<AstNode *>) statement list
 ->                                                     =AgStack<AstNode *>();
 -> statement list:s, statement:x                                  =s.push(x);

/*
 A single statement can be "open" or "closed".

 An "open" statement is a statement that can legally be followed by an "else"
 keyword. A "closed" statement is one that cannot.

 "Open" and "closed" statements are a means for resolving a problem common to
 many programming languages known as the if-then-else ambiguity or "dangling
 else". See www.parsifalsoft.com/ifelse.htm for a discussion of the ambiguity
 and this technique for resolving it.
*/
statement
 -> open statement
 -> closed statement

open statement
 -> if condition:x, statement:s              =AST.node(typeIfStatement, x, s);
 -> if condition:x, closed statement:s1, "else", open statement:s2 =
                                     AST.node(typeIfElseStatement, x, s1, s2);
 -> WHILE, '(', expression:x, ')', open statement:s =
                          PCB.loopDepth--, AST.node(typeWhileStatement, x, s);
 -> FOR, '(', optional expression:init, ';', optional expression:cond,
        ';', optional expression:inc, ')', open statement:s =
              PCB.loopDepth--, AST.node(typeForStatement, init, cond, inc, s);

closed statement
 -> if condition:x, closed statement:s1, "else", closed statement:s2 =
                                        AST.node(typeIfElseStatement,x,s1,s2);
 -> WHILE, '(', expression:x, ')', closed statement:s =
                            PCB.loopDepth--, AST.node(typeWhileStatement,x,s);
 -> FOR, '(', optional expression:init, ';', optional expression:cond,
        ';', optional expression:inc, ')', closed statement:s =
               PCB.loopDepth--, AST.node(typeForStatement,init, cond, inc, s);
 -> simple statement:x                                                     =x;

/*
 A "simple statement" is one that does not end with another statement. All
 simple statements are closed statements and are therefore factored out for
 clarity.
*/
simple statement
 -> DO, statement:s, "while", '(', expression:x, ')', ';' =
                               PCB.loopDepth--, AST.node(typeDoStatement,s,x);
 -> expression:x, ';'                    =AST.node(typeExpressionStatement,x);
 -> ';'                                                   =AST.node(typeNull);
 -> compound statement
 -> "break", ';'                        =PCB.checkLoop(), AST.node(typeBreak);
 -> "continue", ';'                  =PCB.checkLoop(), AST.node(typeContinue);
 -> "return", optional expression:x, ';'             =AST.node(typeReturn, x);
 -> dump statement:ns, ';'                        =AST.listNode(typeDump, ns);
 -> print statement:ns, ';'                      =AST.listNode(typePrint, ns);

(void) DO
 -> "do"                                                     =PCB.loopDepth++;

(void) WHILE
 -> "while"                                                  =PCB.loopDepth++;

(void) FOR
 -> "for"                                                    =PCB.loopDepth++;

if condition
 -> "if", '(', expression:x, ')'                                           =x;

compound statement
 -> '{', statement list:s, '}'           =AST.listNode(typeStatementBlock, s);

// The dump statement accepts a comma delimited list of variable names
(AgStack<AstNode *>) dump statement
 -> "dump", name:k            =AgStack<AstNode *>().push(AST.variableNode(k));
 -> dump statement:ns, ',', name:k              =ns.push(AST.variableNode(k));

// The print statement accepts a comma delimited list of expressions
(AgStack<AstNode *>) print statement
 -> "print", assignment expression:x =           AgStack<AstNode *>().push(x);
 -> print statement:s, ',', assignment expression:x                =s.push(x);

optional expression
 ->                                                       =AST.node(typeNull);
 -> expression

// General expression. As in C, comma expression has the lowest precedence.
expression
 -> assignment expression                      // next higher precedence level
 -> expression:x, ',', assignment expression:y =
                                            AST.node(typeCommaExpression,x,y);

// Assignment expression
assignment expression
 -> conditional expression                     // next higher precedence level
 -> lvalue:lv, assignment op:op, assignment expression:x =
                                                AST.assignmentNode(lv, op, x);

// Conditional expression (ternary operator)
conditional expression
 -> logical or expression                      // next higher precedence level
 -> logical or expression:c, '?', expression:x, ':',
      conditional expression:y     =AST.node(typeConditionalExpression,c,x,y);

// Logical expressions with short-cut evaluation, as in C.
logical or expression
 -> logical and expression                     // next higher precedence level
 -> logical and expression:x, "||", logical or expression:y =
                                      AST.node(typeLogicalOrExpression, x, y);

logical and expression
 -> inclusive or expression                    // next higher precedence level
 -> inclusive or expression:x, "&&", logical and expression:y  =
                                     AST.node(typeLogicalAndExpression, x, y);

// Arithmetic expressions, in operator precedence order.
inclusive or expression
 -> exclusive or expression                    // next higher precedence level
 -> inclusive or expression:x, '|', exclusive or expression:y =
                                                    AST.binaryNode(IOR, x, y);

exclusive or expression
 -> and expression                             // next higher precedence level
 -> exclusive or expression:x, '^', and expression:y =
                                                    AST.binaryNode(XOR, x, y);

and expression
 -> equality expression                        // next higher precedence level
 -> and expression:x, '&', equality expression:y   =AST.binaryNode(AND, x, y);

equality expression
 -> relational expression                      // next higher precedence level
 -> equality expression:x, equality op:op, relational expression:y =
                                                     AST.binaryNode(op, x, y);

relational expression
 -> shift expression                           // next higher precedence level
 -> relational expression:x, relational op:op, shift expression:y =
                                                     AST.binaryNode(op, x, y);

shift expression
 -> additive expression                        // next higher precedence level
 -> shift expression:x, shift op:op, additive expression:y =
                                                     AST.binaryNode(op, x, y);

additive expression
 -> multiplicative expression                  // next higher precedence level
 -> additive expression:x, additive op:op, multiplicative expression:y =
                                                     AST.binaryNode(op, x, y);

multiplicative expression
 -> unary expression                           // next higher precedence level
 -> multiplicative expression:x, multiplicative op:op, unary expression:y =
                                                     AST.binaryNode(op, x, y);

unary expression
 -> factor                                     // next higher precedence level
 -> '+', unary expression:x                                                =x;
 -> unary op:op, unary expression:x                     =AST.unaryNode(op, x);

/*
 Syntactically, we can use ** for exponentiation because we don't have
 pointers. (In C, ** could be confused with pointer indirection.)
 */
factor
 -> primary                                    // next higher precedence level
 -> primary:x, "**", unary expression:y            =AST.binaryNode(POW, x, y);

/*
 Primary expression - bottom level of expression syntax. Variable references,
 constants, the builtin functions. Also, another expression in parentheses.
 (This is how you make parentheses work the way they're supposed to.)
 */
primary
 -> '(', expression:x, ')'                                                 =x;
 -> constant
 -> lvalue:x                                         =AST.unaryNode(FETCH, x);
 -> "++", lvalue:x                                 =AST.unaryNode(I_FETCH, x);
 -> "--", lvalue:x                                 =AST.unaryNode(D_FETCH, x);
 -> lvalue:x, "++"                                 =AST.unaryNode(FETCH_I, x);
 -> lvalue:x, "--"                                 =AST.unaryNode(FETCH_D, x);
 -> function call
 -> '(', "long", ')', primary:x                  =AST.unaryNode(CAST_LONG, x);
 -> '(', "double", ')', primary:x              =AST.unaryNode(CAST_DOUBLE, x);

lvalue
 -> name:n                                               =AST.variableNode(n);

function call
 -> name:k, '(', optional arg list:args, ')'   =AST.functionCallNode(k, args);

(AgStack<AstNode *>) optional arg list
 ->                                                     =AgStack<AstNode *>();
 -> arg list

(AgStack<AstNode *>) arg list
 -> assignment expression:x                     =AgStack<AstNode *>().push(x);
 -> arg list:al, ',', assignment expression:x                     =al.push(x);

constant
 -> integer:x                                            =AST.constantNode(x);
 -> real:x                                               =AST.constantNode(x);
 -> string:x                                             =AST.constantNode(x);
 -> character constant:x                                 =AST.constantNode(x);

// Operator definitions
(Opcode) assignment op
 -> '='                     =STORE;
 -> "+="                    =ADDM;
 -> "-="                    =SUBM;
 -> "*="                    =MULM;
 -> "/="                    =DIVM;
 -> "%="                    =MODM;
 -> "|="                    =IORM;
 -> "&="                    =ANDM;
 -> "^="                    =XORM;
 -> "<<="                   =LSM;
 -> ">>="                   =RSM;
 -> "**="                   =POWM;

(Opcode) equality op
 -> "=="                    =EQ;
 -> "!="                    =NE;

(Opcode) relational op
 -> '<'                     =LT;
 -> "<="                    =LE;
 -> '>'                     =GT;
 -> ">="                    =GE;

 (Opcode) shift op
 -> "<<"                    =LS;
 -> ">>"                    =RS;

(Opcode) additive op
 -> '+'                     =ADD;
 -> '-'                     =SUB;

(Opcode) multiplicative op
 -> '*'                     =MUL;
 -> '/'                     =DIV;
 -> '%'                     =MOD;

(Opcode) unary op
 -> '-'                     =NEG;
 -> '!'                     =NOT;
 -> '~'                     =COM;

/*** LEXICAL UNITS **********************************************************/
digit   = '0-9'
eof     = 0                                          // string null terminator
letter  = 'a-z' + 'A-Z' + '_'
space   =  ' ' + '\t' + '\f' + '\v' + '\r' + '\n'          // blank, tab, etc.

(void) white space
 -> space
 -> "/*", ~eof?..., "*/"                                    // C style comment
 -> "//", ~(eof+'\n')?..., '\n'                           // C++ style comment

/*
	Identifying variable names
  Characters in a name are accumulated in an AgString structure.
*/
(AgString) name
 -> letter:c                                            =AgString().append(c);
 -> name:ns, letter+digit:c                                     =ns.append(c);

// Parsing and evaluating numeric constants

(double) real
 -> simple real
 -> simple real:x, 'e'+'E', signed exponent:e                    =x*pow(10,e);
 -> integer part:x, 'e'+'E', signed exponent:e                   =x*pow(10,e);

(double) simple real
 -> integer part:i, '.', fraction part:f                                 =i+f;
 -> integer part:i, '.'                                                    =i;
 -> '.', fraction part:f                                                   =f;

(double) integer part
 -> decimal integer:x                                                      =x;
 -> hybrid integer:x                                                       =x;
 -> octal integer:x                                           =makeDecimal(x);

(long) signed exponent
 -> '+'?, exponent:x                                                 =(long)x;
 -> '-', exponent:x                                                 =-(long)x;

(double) fraction part
 -> digit:d                                                     =(d-'0')/10.0;
 -> digit:d, fraction part:f                                =(d-'0' + f)/10.0;

(long) integer
 -> decimal integer
 -> octal integer
 -> hex integer

(long) decimal integer
 -> '1-9':d                                                            =d-'0';
 -> decimal integer:x, digit:d                                  =10*x + d-'0';

(long) exponent
 -> '0-9':d                                                            =d-'0';
 -> exponent:x, digit:d                                         =10*x + d-'0';

(long) hybrid integer
 -> octal integer:x, '8-9':d                     =10*makeDecimal(x) + d - '0';
 -> hybrid integer:x, digit:d                                   =10*x + d-'0';

(long) octal integer
 -> '0'                                                                    =0;
 -> octal integer:n, '0-7':d                                   =8*n + d - '0';

(long) hex integer
 -> {"0x" | "0X"}                                                          =0;
 -> hex integer:n, hex digit:d                                      =16*n + d;

(int) hex digit
 -> '0-9':x                                                          =x - '0';
 -> 'a-f' + 'A-F':d                                              =(d & 7) + 9;

// string constant

(Value) string
 -> string element
 -> string:s, string element:e                                          =s+=e;

(Value) string element
 -> '"', s char sequence:b, '"'                                     =Value(b);


(AgString) s char sequence
 ->                                                               =AgString();
 -> s char sequence:s, s char:c                                  =s.append(c);

(int) s char
 -> ~(eof + '"' + '\n' + '\\')
 -> escape sequence

(int) escape sequence
  -> simple escape sequence
  -> octal escape sequence
  -> hexadecimal escape sequence

(int) simple escape sequence
  -> "\\'"   ='\'';
  -> "\\\""  ='"';
  -> "\\?"   = '\?';
  -> "\\\\"  ='\\';
  -> "\\a"   ='\a';
  -> "\\b"   ='\b';
  -> "\\f"   ='\f';
  -> "\\n"   ='\n';
  -> "\\r"   ='\r';
  -> "\\t"   ='\t';
  -> "\\v"   ='\v';

(int) octal escape sequence
  -> one octal | two octal | three octal

(int) one octal
  -> '\\', '0-7':d                                                     =d-'0';

(int) two octal
  -> one octal:n, '0-7':d                                        =8*n + d-'0';

(int) three octal
  -> two octal:n, '0-7':d                                        =8*n + d-'0';

(int) hexadecimal escape sequence
  -> "\\x", hexadecimal digit:d                                            =d;
  -> hexadecimal escape sequence:n, hexadecimal digit:d             =16*n + d;

(int) hexadecimal digit
 -> '0-9':d                                                            =d-'0';
 -> 'A-F' + 'a-f':d                                              =9 + (d & 7);

[
  sticky {one octal, two octal, hexadecimal escape sequence}
]

 // character constant

(int) character constant
 -> '\'', c char:c, '\''                                                   =c;

(int) c char
 -> ~(eof + '\'' + '\n' + '\\')
 -> escape sequence

/*** SUPPORT CODE ***********************************************************/

{ // Begin embedded C++

// Don't use default error handling.
#define SYNTAX_ERROR PCB.reportError()

#define GET_CONTEXT CONTEXT = FileLocation(PCB.pointer, PCB.line, PCB.column)

FileLocation Tree::context() const {
  return PCONTEXT(*pcbPointer);
}

// Function definitions for parser control block

// Constructor
parse_pcb_struct::parse_pcb_struct(const char *text)
  : pointer((const unsigned char *) text), loopDepth(0)
{
  ast.pcbPointer = this;
}

void parse_pcb_struct::checkLoop() {
  if (loopDepth) return;
  char buf[100];
  FileLocation &context = PCONTEXT(*this);
  sprintf(buf, "Error(%d,%d): No loop active", context.line, context.column);
  throw ErrorDiagnostic(buf);
}

// Record syntax error
void parse_pcb_struct::reportError() {
  ag_delete_wrappers(this);
  char buf[100];
  sprintf(buf, "Error(%d,%d): %s", line, column, error_message);
  throw ErrorDiagnostic(buf);
}

// External Interface
AbstractSyntaxTree buildTree(const char *text) {
  parse_pcb_type pcb(text);
  parse(&pcb);
  return pcb.ast;
}

} // End of embedded C++

/*** End of syntax file *****************************************************/