Context-free grammars: Covers, normal forms, and parsing by A. Nijholt

By A. Nijholt

Show description

Read Online or Download Context-free grammars: Covers, normal forms, and parsing PDF

Best programming languages books

TCP/IP Tutorial and Technical Overview

The TCP/IP protocol suite has develop into the de facto regular for desktop communications in modern-day networked international. the ever-present implementation of a particular networking typical has ended in a tremendous dependence at the functions enabled by means of it. at the present time, we use the TCP/IP protocols and the net not just for leisure and knowledge, yet to behavior our enterprise by way of acting transactions, trading items, and providing providers to shoppers.

Sams teach yourself Cobol in 24 hours

Sams educate your self COBOL in 24 Hours teaches the fundamentals of COBOL programming in 24 step by step classes. each one lesson builds at the prior one supplying a superior origin in COBOL programming ideas and strategies. Coupled with the resource code and the compiler on hand from Fujitsu, this hands-on advisor is the simplest, quickest solution to start developing common COBOL compliant code.

CMMI for Development®: Guidelines for Process Integration and Product Improvement (3rd Edition) (SEI Series in Software Engineering)

CMMI® for improvement (CMMI-DEV) describes most sensible practices for the advance and upkeep of goods and providers throughout their lifecycle. via integrating crucial our bodies of data, CMMI-DEV offers a unmarried, finished framework for companies to evaluate their improvement and upkeep methods and enhance functionality.

Additional resources for Context-free grammars: Covers, normal forms, and parsing

Example text

1. ]. 2. 2. Let fG' and h G be parse relations for grammars G' and G, respectively. If G'[f]h]G then G'[f/h]G. Proof. Let ~ be the cover homomorphism under which G'[f/h]G. Define ~R : AG ' AG such that, for any i e AG, , ~R(i) = ~[R if ~(i) = ~[. Then G'[f/h]G under cover homomorphism ~R. D Note, if the cover homomorphism ~ is fine then ~R and @ are identical on % , . Rather loosely formulated one can say that if a cover is supported t by rules of the form A ÷ a or A + e only, then we can treat left and right parses of the covering gra~mmr as being identical.

We show how the elimination of single productions can be done. We use auxiliary 42 sets P0' P! and P2" The set P0 is the set of all the single productions in P. Initially , P| = { A ÷ (i) ~ ! i . A ÷ ~ is in P - P0 }, N' = N and P2 = ~" For any A £ N, if A ~ B ~ y is a derivation in G such that 6 # g and either IYI ~ 2 or y ~ S, then add [A6i] ÷ y <~> to P| and [A6i] to N'. To obtain a left cover, define ~ = 6i. To obtain a right cover, define ~ = i6 R. Notice that since G is cycle-free there are finitely many derivations to consider.

We conclude this section with some notational remarks. In the following table some frequently used names and notations are displayed. We use £ to denote left parses (and left parse relations) and r to denote the right parses. In general, if f denotes a parse relation then f denotes the parse relation {(w,~) I (w, ~R) • f}" Apart from £,r,~ and r the abbreviations £p, standing for left part parses, and £c, standing for left corner parses, will sometimes be used. PARSE RELATION NOTATION NAME f f G'[f/h]G f-to-h cover left left G'[Z/Z]G left cover left i right i G'[£/~]G left-to-right cover right t left G'[~/£]G right-to-left cover G'[r/r]G right cover right right Table IV.

Download PDF sample

Rated 4.89 of 5 – based on 14 votes