“The computer was born to solve problems that did not exist before.”

Random Posts

Monday, November 22, 2021

Formal grammar

Formal grammar

  • Formal grammar is a set of rules. It is used to identify correct or incorrect strings of tokens in a language. The formal grammar is represented as G.
  • Formal grammar is used to generate all possible strings over the alphabet that is syntactically correct in the language.
  • Formal grammar is used mostly in the syntactic analysis phase (parsing) particularly during the compilation.

Formal grammar G is written as follows:

G = <V, N, P, S>  

Where:

N describes a finite set of non-terminal symbols.
V describes a finite set of terminal symbols.
P describes a set of production rules
S is the start symbol.

Example:

  1. L = {a, b}, N = {S, R, B}

Production rules:

  1. S = bR  
  2. R = aR  
  3. R = aB   
  4. B = b

Through this production we can produce some strings like: bab, baab, baaab etc.

This production describes the string of shape banab.

Formal grammar

      Fig: Formal grammar

No comments:

Post a Comment

Post Top Ad

Your Ad Spot

Pages

SoraTemplates

Best Free and Premium Blogger Templates Provider.

Buy This Template