~5.2. Context-free Grammar
A context free grammar (CFG) [1] is used to formalize
the valid sequences of music symbols. A grammar is a set
of rules that describe how a string (or a sequence of symbols) is formed. A context-free grammar (CFG) consists
of terminal, nonterminal, productions, and a start symbol.
In a CFG, one nonterminal is distinguished as the start
symbol. The start symbol is replaced according to productions. After replacement, any remaining nonterminal
can be replaced according to productions, and so on, until
only terminals remain.
For example, we can define S as a whole score and E
as a score element. Then we can define the following: A
score S is a sequence of 1 or more musical elements (E),
optionally followed by a right repeat. A grammar for this
language (set of scores) is:
Starting: S
(G1) S -> E
(G2) S -> E:1
(G3) E -> E E
(G4) E -> b
languages. However, not all context-free grammars can
be parsed by LR(1). Since LR(1) parsers are balanced in
generality and computational efficiency, we often design
grammars acceptable to LR(1) parsers.
5.3. Ambiguity and Error Handling
The problem of ambiguity arises when there are multiple parse trees for the same the sequence of symbols and
the same grammar. For example, if we change production
(G2) to E - E:, we get an ambiguous grammar. The
score b: b: can be generated two ways:
S => E => E E => E:: => b:1 b:
S => E => E => E E:->
F b => E I b I => b b b
The first derivation (line 1) implies a sequence of two
repeated blocks. The second derivation (line 2) implies
nested repeats. Notice that while semantics are not inherent in formal grammars, we often associate semantics
closely with productions and parse trees.
5.4. Syntax Directed Translation and Attribute Grammar
Here, we consider "b" to be a
block, although we could add pr
"b" (now a nonterminal) to termin
start duration)." Based on this CF(
a sequence of symbols is formed
ing derivation. For example, (b,(
well-defined from the grammar be
from S using the productions:
S => E:
=> E E: I
=> ( b, 0, 4 ) ( b, 4, 4 ):
We say that a sequence of syn
score if it can be derived using a g
a derivation is a tree structure wher
a leaf and where each parent node
sponds to a production in the gran
left to right (or more precisely inx
generate the input sequence. The
tree in compilation theory. As an
(b, 0, 4) (b, 0, 4): is shown i
A program that converts a sequ
parse tree is called a parser. A par.
grammar "backwards," reducing a
to the start symbol by applying p
Many parsing algorithms have bee
mars of different complexity. LR
[14] are the most frequently used pa
Fs
Figure 5: Parse tree for (b,
terminal denoting any
oductions that expand
als of the form "(block A syntax-directed definition is a context free grammar toG, we are able to tell if gether with attributes and rules. The attributes are assofrom this grammar us- ciated with grammar symbols and the rules are used to
0, 4 ) (b, 4, 4): is define the relation among symbols [13]. For any termicause we can derive it nal or nonterminal X, denote X.a as some attribute of
X. For a production like X -~ YZ, the rule can be X.a
op(Y.b, Z.c) which contains some attribute symbol, an equal
[use E -> E s]sign and some expression op of Y.b and Z.c.
[use E -> b (twice) ] Define attribute code as the flattened presentation for
all the terminals and nonterminals in our formal control
mbols is a well defined flow framework. Define " " as the concatenation operarammar. The result of tor that links two lists of symbols to be one. For examre each score symbol is ple, if E1.code = (b,0,4) (b,4,4); and E2.code = ||: (b,8,4)
and its children corre-:, then E1.code E2.code = (b,0,4) (b,4,4): (b,8,4):.
amar. The leaves from Furthermore, define attributes "beat" and "dur" to be the
preorder traversal) will starting beat and duration for any terminal or nontermitree is called a parse nal. For any block b, assume b.beat is the "starting beat"
example, the tree for of b and len is the "length" of the block. The syntax din the Figure 5. rected definition for the simple grammar (G1)-(G4) can
ence of symbols into a be defined as follows:
ser essentially runs the
string of nonterminals
)roductions in reverse.
n developed for gram(1) [10] and LALR(1)
arsers for programming,0,4) (b,4,4)
Starting: S
(G1) S ->
(1.1) S.
(1.2) 5.
(1.3) 5.
(G2) S ->
(2.1) S.
(2.2) S.
(2.3) S.
(G3) E ->
(3.1) E.
(3.2) E.
(3.3) E.
(G4) E ->
(4.1) E.
(4.2) E.
(4.3) E.
E.code=.beat
dur =
E EI.code=.beat
dur =
F E.code=.beat
dur =
code=
beat=
dur=
{
F. code
F. beat
F. dur
{
E.code E.code
SE.beat
E.dur + E.dur
}
}
{
= E1.code E2.code
= E1.beat
E1.dur + E2.dur }
= (b, b.beat, b.dur)
= b.beat
b.dur }
312 2013 ICMC
