SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 131:
Line 131: − Chomsky defined 4 grammar levels; level 3 is a subset of level 2, which is a subset of level 1, which is a subset of level 0. The higher the level number, the simpler the generated language is, while the lower the level number the more difficult it is to parse a sentence in that language.+ − + + + + + + + + + + + + + +
→Chomsky hierarchy: table summarising Chomsky grammars
==Chomsky hierarchy==
==Chomsky hierarchy==
By imposing different constraints
<ref>{{cite web
<ref>{{cite web
| url = http://www.cs.uaf.edu/2011/spring/cs331/lectures/cs331_20110124_grammar.html
| url = http://www.cs.uaf.edu/2011/spring/cs331/lectures/cs331_20110124_grammar.html
| title = Lecture notes: Languages & Grammars
| title = Lecture notes: Languages & Grammars
| accessdate = 2012-04-07
| accessdate = 2012-04-07
}}</ref>
}}</ref>
as to what sort of transformation rules could be used, Chomsky was able to define four strictly nested transformational grammars, which he numbered from 0 to 3. As the grammar number increases, the generated language becomes simpler. As the grammar number decreases, parsing a sentence in that language becomes more difficult. The following table provides a summary, which is then explained further in the subsequent subsections.
{| class="wikitable"
!| Chomsky<br>number || linguistic name || Rule constraints || Recogniser || Notes
|-
| 0 || recursively enumerable || [anything] -> [anything] || Turing machine || most human languages
|-
| 1 || context-sensitive || X ''A'' Y -> X [anything] Y || linear bounded automaton || X and Y provide the context in which ''A'' can be transformed
|-
| 2 || context-free || ''A'' -> [anything] || non-deterministic push-down automaton || syntax analysis for most programming languages
|-
| 3 || regular || ''A'' -> [nothing]<br>''A'' -> '''xyz'''<br>''A'' -> '''xyz''' ''B'' || finite automaton || lexical analysis (combining characters into words/tokens)
|}
===Level 0===
===Level 0===