SkipCaptcha
265
edits
Changes
Jump to navigation
Jump to search
Line 205:
Line 205: − + − + Line 214:
Line 214: − ''Expression'' -> ''Term'' − ''Expression'' -> ''Expression'' ''AddSubOp'' ''Term'' − ''Term'' -> ''Primary'' − ''Term'' -> ''Term'' ''MulDivOp'' ''Primary'' − + − + − + − + − + − + + + + + +
→Example: add comments to formal grammar
====Example====
====Example====
The following example shows how context-free grammars can cope with arithmetic expressions involving possibly nested brackets. Also an expression such as "2 + 3 * 4" could be interpreted as either "(2 + 3) * 4" or as "2 + (3 * 4)". The latter interpretation is that which is normally used - multiplication "*" is said to have a higher priority than addition "+" - so the example also needs to incorporate this priority concept into the grammar. Furthermore, consecutive operators of the same priority are applied from left to right, so that "8 - 2 + 3" is interpreted as "(8 - 2) + 3" = 9, rather than as "8 - (2 + 3)" = 3. This ordering must also be built in to the grammar.
The following example shows how context-free grammars can cope with arithmetic expressions involving possibly nested brackets. Also an expression such as "2 + 3 * 4" could be interpreted as either "(2 + 3) * 4" or as "2 + (3 * 4)". The latter interpretation is that which is normally used - multiplication "*" is said to have a higher priority than addition "+" - so the example also needs to incorporate this priority concept into the grammar. Furthermore, consecutive operators of the same priority are applied from left to right, so that "8 - 2 + 3" is normally interpreted as "(8 - 2) + 3" = 9, rather than as "8 - (2 + 3)" = 3. This ordering must also be built in to the grammar.
To avoid distracting side-issues, this example only deals with numbers which consist solely of a single digit. The example is a simplified version of the definition of an arithmetic expression given in the Revised Algol 60 Report (Section 3.3.1)
To avoid distracting side-issues, this example only deals with numbers which consist solely of a single digit. The example is a simplified version of the definition of an arithmetic expression given in the Revised Algol 60 Report (Section 3.3.1).
<ref>{{cite web
<ref>{{cite web
| url = http://www.masswerk.at/algol60/report.htm
| url = http://www.masswerk.at/algol60/report.htm
}}</ref>
}}</ref>
''Primary'' -> ''Number''
''Expression'' -> ''Term'' # an ''Expression'' is either a ''Term''
''Primary'' -> '''(''' ''Expression'' ''')'''
''Expression'' -> ''Expression'' ''AddSubOp'' ''Term'' # or an ''Expression'' followed by '''*''' or '''/''' followed by a ''Term''
''Term'' -> ''Primary'' # a ''Term'' is either a ''Primary''
''MulDivOp'' -> '''*'''. '''/'''
''Term'' -> ''Term'' ''MulDivOp'' ''Primary'' # or a ''Term'' followed by '''+''' or '''-''' followed by a ''Primary''
''AddSubOp'' -> '''+'''. '''-'''
#
''Number'' -> '''0''', '''1''', ... '''9'''
''Primary'' -> ''Number'' # a ''Primary'' is either a ''Number''
''Primary'' -> '''(''' ''Expression'' ''')''' # or an ''Expression'' enclosed in brackets
#
''MulDivOp'' -> '''*'''. '''/''' # multiplication and division have the same priority
''AddSubOp'' -> '''+'''. '''-''' # addition and subtraction have the same priority
''Number'' -> '''0''', '''1''', ... '''9''' # this simple-minded definition of a ''Number'' is enough for this example
===Level 1===
===Level 1===