Chapter two grammar and language

2.1 grammar

A grammar is a set of formal rules that define or describe the structure of a grammar.

(1) Formal definition of grammar:

G[S]=(Vn, Vt, P, S)

Non-empty finite non-terminal set VN, non-empty finite terminal set VT, beginning symbol S, production set P)Copy the code

2.2 language

(1) Derivation and specification

One step derivation is called direct derivation, one or more steps derivation is called forward derivation, and zero or more steps derivation is called star derivation.

The leftmost derivation expands the leftmost non-terminal in each step, and the rightmost derivation expands the rightmost non-terminal in each step. The rightmost derivation is also known as the canonical derivation.

The convention is the inverse of derivation, the left-most derivation is the right-most derivation, and the left-most derivation is the left-most specification, which is also called the specification.

(2) Sentence patterns, sentences and language

Has grammar G [S] : S – > Ab | C, A – > Aa | \ varepsilon, C – > C

The string of symbols derived by S is the sentence pattern of grammar G.

For example, Ab is a sentence pattern;

The string of symbols with only terminators derived by S is the sentence of grammar G.

For example, c is a sentence;

A grammatical language is a collection of all grammatical sentences, denoted L(G).

Two grammars are said to be equivalent if they define the same language.

2.3 the syntax tree

Syntax tree is an intuitive tool to describe the derivation of context-free grammatical patterns, also known as the derivation tree, syntax analysis tree.

Given the grammar G, a grammar tree can be constructed for any sentence pattern of G.

The root of the syntax tree is the start symbol.

If the direct descendants of node A are aBcd from left to right, then A->aBcd must be A production of this method.

At any point in the growth of the grammar tree, all the leaves are lined up from left to right to form a sentence pattern.

In a grammar, a sentence is ambiguous if it can have more than one syntax tree. If a grammar contains ambiguous sentences, the textual method is ambiguous.

Right hand side derivation

The syntax tree

2.4 the sentence pattern

N =E+T*F+ I

The syntax tree

(1) Phrase (indirect subtree)

Phrase n relative to E (subtree of E1) : E2+T3*F3;

I is a phrase relative to T1

(2) Direct phrase (direct subtree)

TF is the direct phrase of sentence pattern n relative to the production form T — >TE.

I is the direct phrase of sentence pattern n relative to the production formula F — > I

(3) Handle

Definition: The leftmost direct phrase of a sentence pattern becomes the handle of the sentence pattern