Parsing Transformative LR(1) Languages

Computer Science – Programming Languages

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-71429

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.