Computer Science – Programming Languages
Scientific paper
2006-05-24
Computer Science
Programming Languages
68 pages, 4 figures. Numerous stylistic and grammatical fixes; new material in Sections 2.2 and 4.2
Scientific paper
We consider, as a means of making programming languages more flexible and powerful, a parsing algorithm in which the parser may freely modify the grammar while parsing. We are particularly interested in a modification of the canonical LR(1) parsing algorithm in which, after the reduction of certain productions, we examine the source sentence seen so far to determine the grammar to use to continue parsing. A naive modification of the canonical LR(1) parsing algorithm along these lines cannot be guaranteed to halt; as a result, we develop a test which examines the grammar as it changes, stopping the parse if the grammar changes in a way that would invalidate earlier assumptions made by the parser. With this test in hand, we can develop our parsing algorithm and prove that it is correct. That being done, we turn to earlier, related work; the idea of programming languages which can be extended to include new syntactic constructs has existed almost as long as the idea of high-level programming languages. Early efforts to construct such a programming language were hampered by an immature theory of formal languages. More recent efforts to construct transformative languages relied either on an inefficient chain of source-to-source translators; or they have a defect, present in our naive parsing algorithm, in that they cannot be known to halt. The present algorithm does not have these undesirable properties, and as such, it should prove a useful foundation for a new kind of programming language.
No associations
LandOfFree
Parsing Transformative LR(1) Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parsing Transformative LR(1) Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parsing Transformative LR(1) Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-71429