Resurrecting Object Curry - Part 3 : New/Experimental Parsing Algorithm.

In part two I talked about using parsing strategy that is inspired from Generalized Phrase Structure Grammar.  In Object Curry compiler I am going to use a new and experimental strategy.

Separation of Immediate Dominance and Linear Precedence

In BNF form of grammar the production rules are given in the following manner
A ::= B C D
Where A is a parent and it can have three child nodes in that order.
However my parsing strategy will separate immediate  dominance and linear precedence.
To best of my knowledge no one has attempted to define parsing strategy and grammar specification as defined below..


Immediate Dominance : In simple terms it says A is the parent of B, C and D . It does not specify in which order  B, C, D should occur.
Eg Rule A--> B, C, D specifies that A can have three children

Linear Precedence : Specifies order in which children are. Orders can be partially specified
Eg Rule  B < C specifies that under A,  B must occur before  C

Head Identifying Rule: Each such production has exactly one head element and must occur in the production.
Eg.  ConditionalBlock ~ IfClause

if {} is valid
if {} else {} is valid
but else {} is not because the head is missing.


[place holder for the diagram]

Example is
QueryExpression --> SelectClause, WhereClause, FromClause.

With the separation of Dominance and Precedence all of following are valid production of the rules.

select * from tbl where col == 10;
from tbl where col ==10 select *;
...

Syntax Directed Translation and Attribute Value Calculation.

The values of attributes at each node in a syntax tree is calculated in following manner.
Synthesized attributes : Values of the parent is a function of values of its children.
Eg.  In expression   from x join y , the value of tuple type is determined by value of its children

Inherited Attributes: Attribute value is inherited from parents to the children.
In java like try catch block the closable variables are inherited.

Inferred attributes : The attributes are calculated using rules that are applicable to only nodes that have certain properties.

Algorithm
1. Variant of recursive descent for creating syntax tree.
2.  Topological sort based evaluation of dependency graph of attribute values.

I might stumble upon unexpected problem.

Useful References : 
[1] Generalized Phrase Structure Grammar by Gazdar,Klien, Pullum and Sag
 - Book about theory of natural languages!
 - chapter 3 , nature of grammatical rules.
[2] Compilers : Principles, Techniques and Tools by Aho, Sethi, Ullman
- the compiler book
- chapter 5,  Syntax directed translation.