Editing Chomsky normal form (section)

==Example==

[[File:Syntax tree of arithmetic expression wrt Chomsky normal form grammar.gif|thumb|[[Abstract syntax tree]] of the [[expression (mathematics)|arithmetic expression]] "''a''^2+4*''b''" wrt. the example grammar ('''top''') and its Chomsky normal form ('''bottom''')]]
The following grammar, with start symbol ''Expr'', describes a simplified version of the set of all syntactical valid arithmetic expressions in programming languages like [[C (programming language)|C]] or [[Algol60]]. Both ''number'' and ''variable'' are considered terminal symbols here for simplicity, since in a [[compiler front-end|compiler front end]] their internal structure is usually not considered by the [[parser]]. The terminal symbol "^" denoted [[exponentiation]] in Algol60.

:{|
|-
| ''Expr'' 
| → ''Term'' 
| | |  ''Expr'' ''AddOp'' ''Term''
| | | ''AddOp'' ''Term''  
|-
| ''Term'' 
| → ''Factor''  
| | |  ''Term'' ''MulOp'' ''Factor''
|-
| ''Factor'' 
| → ''Primary''  
| | |  ''Factor'' ^ ''Primary''
|-
| ''Primary'' 
| → ''number''  
| | |  ''variable''  
| | |  ( ''Expr'' )
|-
| ''AddOp''
| → +
| | | &minus;
|-
| ''MulOp''
| → *
| | | /
|}

In step "START" of the [[#Converting a grammar to Chomsky normal form|above]] conversion algorithm, just a rule ''S''<sub>0</sub>→''Expr'' is added to the grammar.
After step "TERM", the grammar looks like this:

:{|
|-
| ''S''<sub>0</sub>
| → ''Expr'' 
|-
| ''Expr'' 
| → ''Term'' 
| | |  ''Expr'' ''AddOp'' ''Term''
| | | ''AddOp'' ''Term''  
|-
| ''Term'' 
| → ''Factor''  
| | |  ''Term'' ''MulOp'' ''Factor''
|-
| ''Factor'' 
| → ''Primary''  
| | |  ''Factor'' ''PowOp'' ''Primary''
|-
| ''Primary'' 
| → ''number''  
| | |  ''variable''  
| | |  ''Open'' ''Expr'' ''Close''
|-
| ''AddOp''
| → +
| | | &minus;
|-
| ''MulOp''
| → *
| | | /
|-
| ''PowOp''
| → ^
|-
| ''Open''
| → (
|-
| ''Close''
| → )
|}

After step "BIN", the following grammar is obtained:

:{|
|-
| ''S''<sub>0</sub>
| → ''Expr'' 
|-
| ''Expr'' 
| → ''Term'' 
| | |  ''Expr'' ''AddOp_Term''
| | | ''AddOp'' ''Term''  
|-
| ''Term'' 
| → ''Factor''  
| | |  ''Term'' ''MulOp_Factor''
|-
| ''Factor'' 
| → ''Primary''  
| | |  ''Factor'' ''PowOp_Primary''
|-
| ''Primary'' 
| → ''number''  
| | |  ''variable''  
| | |  ''Open'' ''Expr_Close''
|-
| ''AddOp''
| → +
| | | &minus;
|-
| ''MulOp''
| → *
| | | /
|-
| ''PowOp''
| → ^
|-
| ''Open''
| → (
|-
| ''Close''
| → )
|-
| ''AddOp_Term''
| colspan=3 | → ''AddOp'' ''Term''
|-
| ''MulOp_Factor''
| colspan=3 | → ''MulOp'' ''Factor''
|-
| ''PowOp_Primary''
| colspan=3 | → ''PowOp'' ''Primary''
|-
| ''Expr_Close''
| colspan=3 | → ''Expr'' ''Close''
|}

Since there are no ε-rules, step "DEL" does not change the grammar.
After step "UNIT", the following grammar is obtained, which is in Chomsky normal form:

:{|
|-
| ''S''<sub>0</sub>
| → ''number'' 
| | |  ''variable'' 
| | |  ''Open'' ''Expr_Close''
| | |  ''Factor'' ''PowOp_Primary''
| | |  ''Term'' ''MulOp_Factor''
| | |  ''Expr'' ''AddOp_Term''
| | | ''AddOp'' ''Term''  
|-
| ''Expr'' 
| → ''number'' 
| | |  ''variable'' 
| | |  ''Open'' ''Expr_Close''
| | |  ''Factor'' ''PowOp_Primary''
| | |  ''Term'' ''MulOp_Factor''
| | |  ''Expr'' ''AddOp_Term''
| | | ''AddOp'' ''Term''  
|-
| ''Term'' 
| → ''number'' 
| | |  ''variable'' 
| | |  ''Open'' ''Expr_Close''
| | |  ''Factor'' ''PowOp_Primary''
| | |  ''Term'' ''MulOp_Factor''
|-
| ''Factor'' 
| → ''number'' 
| | |  ''variable'' 
| | |  ''Open'' ''Expr_Close''
| | |  ''Factor'' ''PowOp_Primary''
|-
| ''Primary'' 
| → ''number''  
| | |  ''variable''  
| | |  ''Open'' ''Expr_Close''
|-
| ''AddOp''
| → +
| | | &minus;
|-
| ''MulOp''
| → *
| | | /
|-
| ''PowOp''
| → ^
|-
| ''Open''
| → (
|-
| ''Close''
| → )
|-
| ''AddOp_Term''
| colspan=3 | → ''AddOp'' ''Term''
|-
| ''MulOp_Factor''
| colspan=3 | → ''MulOp'' ''Factor''
|-
| ''PowOp_Primary''
| colspan=3 | → ''PowOp'' ''Primary''
|-
| ''Expr_Close''
| colspan=3 | → ''Expr'' ''Close''
|}

The ''N''<sub>''a''</sub> introduced in step "TERM" are ''PowOp'', ''Open'', and ''Close''.
The ''A''<sub>''i''</sub> introduced in step "BIN" are ''AddOp_Term'', ''MulOp_Factor'', ''PowOp_Primary'', and ''Expr_Close''.