+(reset)-

Theory

Practice

Grammatical dissection

In this part you will learn different methods of dissection in the languages ​​of formal grammar.

Analysis sentences

Sentence diagram is a pictorial representation of the gramatical structure of a natural-language sentence. A sentence diagram is a form of a parse tree.

Example

we have grammar G = <{E},{i,+,*},{E::=E+E|E*E|(E)|i},E>

N ={E}
V ={i,+,*}
P ={E::= E+E|E*E|(E)|i}
S = E

Sentence i+i*i belongs to the language L(G) generated by this grammar.

  1. E =>E + E =>E + E * E =>i + E * E =>i + i * E =>i + i * i
  2. E =>E + E =>E + E * E =>E + E * i =>E + i * i =>i + i * i
  3. E =>E * E =>E + E * E =>i + E * E =>i + i * E =>i + i * i

For each extraction,there is exactly one syntactic tree. For arguments 1 and 2 trees are identical,which means that these arguments are equivalent:

For the extraction 3 we can create the following syntactic tree:

This grammar is ambiguous,because in the case of propositional forms of E + E * E is not known whether the first action is E + E or E * E (both of these arguments are equal.)

Ambiguous grammar is grammar whose language contains at least one ambiguous sentence. Grammar of the sentences containing no ambiguous grammar is unambiguous.

Ambiguous sentence is the sentence for which there is more than one syntactic tree.

The characteristic of uniqueness,or ambiguity in assigning the grammar,not language,it is generated. Often,for a language grammar,we can derive both ambiguous and unambiguous. However,there are languages ​​for which a clear definition of grammar is not possible. We call these languages ​​significantly ambiguous

Methods of grammatical dissection

  • method of right and left
  • generation method
  • reduction method

Generation method

In this method we start analysis from a distinguished start symbol of grammar,using the rules productions of the left non-terminal symbol.

Example

We have grammar G = <N,V,P,S>

N ={N,D}
V ={0,1,2,3,4,5,6,7,8,9}
P ={N ->ND|D,D->0|1|2|3|4|5|6|7|8|9}
S = N

and sentence:35

dissection by the generation method:

N =>ND =>DD =>3D =>35

Reduction method

The method of reduction,by successive reductions analyzed at a particular stage form of propositional come finally to the distinguished symbol of the grammar.

dissection by the reduction method:

35 <= D5 <=N5 <= ND <= N

Questions

  • When the two extractions are equivalent?
  • Is the grammar unambiguous sentences can occur,for which we can generate more than one syntactic tree?
  • How different is the method of reduction from the generation method?

If you do not know the answer to these questions,read again the above content.