Production rules in context free grammar are specified in the following way.
V → w
Where V is a single non terminal symbol, and w is a string of terminals and or non terminal symbols. w can also be empty. My understanding is that when some text is parsed, these rules are applied, such that 'w' can be replaced by V in the AST.
Languages that are described by context free grammars exhibit block structure. This means that sentences are recursively composed of smaller phrases, and eventually words or word elements.
A context free grammar provides a simple and mathematically precise way for describing the methods in which phrases can be built from smaller blocks, and for capturing those phrases.
Block structure was introduced in computer programming languages in the Algol project.
context free grammars allow the construction of parsing algorithms which, for a given String, can determine if and whether it can be constructed using the rules of the grammar. Notice that we talk of the String being constructed from the grammar rules, and not the other way around.
Formal definition of context free grammar:
A context-free grammar G is defined by the 4-tuple:
Where
V - A set of non terminal symbols. Each such symbols represents a different type of clause or phrase in the sentence.
- Is a finite set of terminals, disjoint from V (also called the alphabet of the language).
- Is the set of rewrite rules with a non terminal on the LHS and a string of non terminals and terminals on the RHS. 
- Is the start variable used to represent the whole sentence. It must be part of V.Questions:
- Need to understand the difference between context free and context sensitive grammar?
Insights:
- The * category of symbols (in EBNF) can also be represented as recursion in BNF.
No comments:
Post a Comment