1
$\begingroup$

I was going through the text Compilers: Principles,Techniques and Tools by Ullman et. al. where I came across the claim in the question by authors. Below is the definition and following it is the claim by the authors.


Form of a Syntax-Directed Definition

In a syntax-directed definition, each grammar production $A\rightarrow \alpha$ has associated with it a set of semantic rules of the form $b := f(c_1, c_2, . . . , c_k)$ where $f$ is a function, and either

  1. $b$ is a synthesized attribute of $A$ and $c_1, c_2, . . . , c_k$ are attributes belonging to the grammar symbols of the production, or

  2. $b$ is an inherited attribute of one of the grammar symbols on the right side of the production, and $c_1, c_2, ... , c_k$ are attributes belonging to the grammar symbols of the production.


Claim:

In a syntax-directed definition, terminals are assumed to have synthesized attributes only, as the definition does not provide any semantic rules for terminals. Values for attributes of terminals are usually supplied by the lexical analyzer.

That values of the terminals is provided by the lexical analyzer is a usual practice.(Which makes us assume that terminals have synthesized attributes usually). But cannot understand their claim, with the logic that the definition does not allow it. Going by point $2$ in the definition:

$b$ is an inherited attribute of one of the grammar symbols on the right side of the production: so the right hand side of a production might as well contain terminals, making $b$ an inherited attribute of a terminal.

The point $1$ applied to $b$ which is an attribute of a symbol(non terminal) on the LHS and only point $1$ talks about synthesized attributes, so $1$ makes no provisions for attributes for the non terminals. Hence there is no provision of synthesized attributes for the terminals.

Is this something like this?

$\endgroup$

1 Answer 1

1
$\begingroup$

It's not a claim; it's a definition. In mathematics, we can define things however we want. Humpty Dumpty by Lewis Carrol, image by Tenniel: When I use a word, it means just what I choose it to mean -- neither more nor less [See Note 1]

Our only obligation is to make sure we've shared the definition with our readers.

In any event, it doesn't make the slightest difference. If we want to define an inherited attribute for a terminal, we can just replace the terminal throughout the grammar with a non-terminal with a single production whose right-hand side consists only of the terminal. Then the surrogate non-terminal can carry whatever attributes we want it to carry.

This transformation does not in any way affect the parse (provided it is done consistently throughout the grammar).


Notes

  1. It's not a coincidence that Lewis Carroll was a mathematics professor.
$\endgroup$
1
  • $\begingroup$ Aah, thanks for the nice pictorial answer... $\endgroup$ Mar 29, 2021 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.