Search code examples
semanticscontext-free-grammarrules

Attributes of semantic rules

I've these rules:

S -> I#A
I -> a
I -> b
A -> aA
A -> bA
A -> EPSILON

This grammar produces a sequence of a's and b's. They are preceded by a single a (or a single b) and an #. I need to define semantic rules which gives me the number of a's or b's (it depends on which one I choose before the #) after the #. I don't know how to start because the value of A (in the first rule) depends on the value of I. How do I pass 'a' or 'b' to A?

Solution

  • I'm not 100% sure what the question is, but as in the comment the grammar is used to read in a string. You can look at the rules as if they are describing a tree where the left hand side is the parent and the right hand side are the children.

    So in your system there seems to be an alphabet which consists of {a, b, EPSILON, #}. Therefore if you have the input string of a#b you would get the following tree

    S ---  I -- a
  ---  #
  ---  A -- b
         -- A -- EPSILON

    So S has the children of I, # and A ( S -> I # A), I has a child of a (I -> a). A has two children b and A (A -> b A) and the last A has a single child EPSILON

    After this you can then add in semantic rules such as conditions to your grammar also known as an attribute grammar.