What are the parsing algorithms for programmed grammars?

Question

I want to know what are the parsing algorithms used for parsing programmed grammars. Any Links , blogs or anything where i can read about programmed grammars and there parsing algorithms except IEEE research papers ?

Answer 1

I think it's explained well in The power of programmed grammars with graphs from various classes:

A context-free grammar is specified as a quadruple G = (N, T, S, P), where N is a finite non-empty set called the nonterminal alphabet, T is a finite non-empty set called the terminal alphabet (N ∩ T = ∅), S ∈ N is the start symbol, and P is a finite subset of N × (N ∪ T)∗ called the set of rules. Rules are also named as productions.

A programmed grammar (without appearance checking) is a six-tuple G = (N, T, S, Lab, P, PG) where N , T and S are specified as in a context-free grammar, Lab is an alphabet (of labels), P is a finite set of context-free rules called the set core productions, and PG is a finite set of triples r = (q, p, σ), where q ∈ Lab is the label of r, p ∈ P is a context-free production called the core production of r, and σ is a subset of Lab and is termed the success field of r. The elements of PG are called the rules of G.

The language L(G) generated by a programmed grammar G specified as above is defined as the set of all words w ∈ T∗ such that there is a derivation S = w0 =⇒r1 w1 =⇒r2 w2 =⇒r3 . . . =⇒rk wk = w, where k ≥ 1 and, for 1 ≤ i ≤ k, wi−1 = wi−1 Ai wi−1 and wi = wi−1 vi wi−1 for some words wi−1 , wi−1 ∈ (N ∪ T)∗ , ri = (qi , Ai → vi , σi) and, for i < k, qi+1 ∈ σi.

Excuse the lack of LaTeX.

In a similar way that Ogden's Lemma is stronger than the Pumping Lemma (because of markings), the concept of programmed grammar is stricter than context-free because of these labellings.