Analytic Grammar

In ) Alphabet . Formal grammars are so named by analogy to Grammar in human languages.

Formal grammars fall into two main categories: ''generative'' and ''analytic''.

A Generative Grammar , the most well-known kind, is a set of rules by which all possible Strings in the language to be described can be ''generated'' by successively Rewriting strings starting from a designated start symbol. A generative grammar in effect formalizes an Algorithm that ''generates'' strings in the language.

An analytic grammar, in contrast, is a set of rules that assume an arbitrary string to be given as ''input'', and which successively ''reduce'' or ''analyze'' that input string yielding a final Boolean , "yes/no" result indicating whether or not the input string is a member of the language described by the grammar. An analytic grammar in effect formally describes a Parser for a language.

In short, an analytic grammar describes how to ''read'' a language, whereas a generative grammar describes how to ''write'' it.

GENERATIVE GRAMMARS

A generative grammar consists of a set of rules for transforming strings. To generate a string in the language, one begins with a string consisting of only a single "start" symbol, and then successively applies the rules (any number of times, in any order) to rewrite this string. The language consists of all the strings that can be generated in this manner. Any particular sequence of legal choices taken during this rewriting process yields one particular string in the language, and if there are multiple different ways of generating a single string, then the grammar is said to be Ambiguous .

For example, assume the alphabet consists of '

a

' and '

b

', the start symbol is '

S

' and we have the following rules:

: 1.

S \longrightarrow aSb

: 2.

S \longrightarrow ba

then we start with "

S

", and can choose a rule to apply to it. If we choose rule 1, we replace '

S

' with '

aSb

' and obtain "

aSb

". If we choose rule 1 again, we replace '

S

' with '

aSb

' and obtain "

aaSbb

". This process is repeated until we only have symbols from the alphabet (i.e., '

a

' and '

b

'). Finishing off our example, if we now choose rule 2, we replace '

S

' with '

ba

' and obtain "

aababb

", and are done. We can write this series of choices more briefly, using symbols:

S \longrightarrow aSb \longrightarrow aaSbb \longrightarrow aababb

. The language of the grammar is the set of all the strings that can be generated using this process:

\left \{ba, abab, aababb, aaababbb, ...
ight \}

.

Formal definition

In the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s , a grammar ''G'' consists of the following components:

A finite set $N$ of ''nonterminal symbols''.

A finite set $\Sigma$ of ''terminal symbols'' that is Disjoint from $N$ .

A finite set $P$ of ''production rules'' where a rule is of the form

} \longrightarrow string in $(\Sigma \cup N)^{---}$

} is the Kleene Star and $\cup$ is Union ) with the restriction that the left-hand side of a rule (i.e., the part to the left of the $\longrightarrow$ ) must contain at least one nonterminal symbol.

A symbol $S$ in $N$ that is indicated as the ''start symbol''.

G

(N, \Sigma, P, S)

The ''language'' of a formal grammar

G = (N, \Sigma, P, S)

, denoted as

\boldsymbol{L}(G)

, is defined as all those strings over

\Sigma

that can be generated by starting with the start symbol

S

and then applying the production rules in

P

until no more nonterminal symbols are present.

Example

''For these examples, formal languages are specified using Set-builder Notation .''

Consider, for example, the grammar

G

with

N = \left \{S, B
ight \}

\Sigma = \left \{a, b, c
ight \}

P

consisting of the following production rules

: 1.

S \longrightarrow aBSc

: 2.

S \longrightarrow abc

: 3.

Ba \longrightarrow aB

: 4.

Bb \longrightarrow bb

and the nonterminal symbol

S

as the start symbol. Some examples of the derivation of strings in

\boldsymbol{L}(G)

are:

$\boldsymbol{S} \longrightarrow (2) abc$

$\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (2) a\boldsymbol{Ba}bcc \longrightarrow (3) aa\boldsymbol{Bb}cc \longrightarrow (4) aabbcc$

$\boldsymbol{S} \longrightarrow (1) aB\boldsymbol{S}c \longrightarrow (1) aBaB\boldsymbol{S}cc \longrightarrow (2) a\boldsymbol{Ba}Babccc \longrightarrow (3) aaB\boldsymbol{Ba}bccc\longrightarrow (3) aa\boldsymbol{Ba}Bbccc$ $\longrightarrow (3) aaaB\boldsymbol{Bb}ccc \longrightarrow (4) aaa\boldsymbol{Bb}bccc \longrightarrow (4) aaabbbccc$

(where the used production rules are indicated in brackets and the replaced part is each time indicated in bold).

"http://wwwinformationdelightinfo/encyclopedia/entry/Vrhbosna/context-free_grammar" class="copylinks">Context-free Grammar s, the left hand side of a production rule may only be formed by a single non-terminal symbol The language defined above is not a context-free language, but for example the language <math>\left \{ a^{n}b^{n} n > 0 ight \}</math> (any positive number of 'a's followed by the same number of 'b's) is, as it can be defined by the grammar <math>G2</math> with <math>N=\left \{S ight \}</math>, <math>\Sigma=\left \{a,b ight \}</math>, <math>S</math> the start symbol, and the following production rules:

The Language Defined Above Is Not Regular, But The Language <math>\left \{ A^{n}b^{m} M,n > 0 Ight \}</math> (any Positive Number Of 'a's Followed By Any Positive Number Of 'b's, Where The Numbers May Be Different) Is, As It Can Be Defined By The Grammar <math>G3</math> With <math>N

\left \{S, A,B ight \}</math>, <math>\Sigma=\left \{a,b ight \}</math>, <math>S</math> the start symbol, and the following production rules:

Information About

Analytic Grammar