SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 253:
Line 253: + + − + + + + + + + − For context-sensitive grammars the left-hand side of a rule may indicate the context in which that rule applies, so that the same non-terminal item may be transformed in different ways depending on the context in which it appears. Several examples appear in these lecture notes.+ + +
→Chomsky hierarchy: further discussion, rules for level 1 grammars
====Discussion====
====Discussion====
Context-free grammars (or equivalent definitions using Backus-Naur-Form) are widely used both to define the syntax of programming languages and to (semi-automatically) generate parsers for these languages.
Context-free grammars (or equivalent definitions using Backus-Naur-Form) are widely used both to define the syntax of programming languages and to (semi-automatically) generate parsers for these languages.
A limitation/feature of both regular grammars and context-free grammars is that the left-hand side of any rule is always a single non-terminal item, so any transformation is applied regardless of the context in which that non-terminal item appears. A simple example which depends on context is the use of singular and plural nouns and verbs in English. We say: '''the man runs''' or '''the men run''', but not either of '''the man run''' or '''the men runs'''. Which form of verb to use depends on the noun, i.e. there is a context dependency.
===Level 1===
===Level 1===
For both regular grammars and context-free grammars, the left-hand side of any rule is always a single non-terminal item, and any transformation is applied regardless of the context in which that non-terminal item appears.
For context-sensitive grammars the left-hand side of a rule may indicate the context in which that rule applies, so that the same non-terminal item may be transformed in different ways depending on the context in which it appears.
There is only one transformation rule for context-sensitive grammars:
X [non-terminal] Y -> X [anything] Y
where X and Y determine the context in which the [non-terminal] is transformed. Note that X and Y may each be terminals or non-terminals or [nothing].
====Example====
Several examples appear in these lecture notes.
<ref>{{cite web
<ref>{{cite web
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| url = http://www.divms.uiowa.edu/~fleck/taylor.pdf
| title = Context-sensitive Examples
| title = Context-sensitive Examples
| author = Taylor
| accessdate = 2012-04-26
| accessdate = 2012-04-26
}}</ref>
}}</ref>