Table of contents

Introduction

Recursive-Descent Parsing

2.1.

Example

On-The-Fly Code Generation

L-Attributed SDD and LL Parsing

Bottom-Up Parsing

5.1.

Example

Frequently Asked Questions

6.1.

What is a synthesized attribute?

6.2.

What is an inherited attribute?

6.3.

What is L-attributed SDT?

6.4.

What is SDD?

6.5.

What are the different techniques to implement L-attributed SDD? Name them.

Conclusion

Last Updated: Mar 27, 2024

Implementing L-Attributed SDD's

Q: What is a synthesized attribute?

A synthesised attribute is a non-terminal attribute on the left side of a production. Synthesised attributes represent the information that is transmitted up the parse tree. Only its children can provide value to the attribute.

Q: What is L-attributed SDT?

An L-attributed SDT employs both synthesised and inherited attributes with the constraint that the inherited attribute can only inherit values from left siblings.

Author Aditya Kumar

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

L-Attributed definitions are the L-Attribute class of Syntax Directed Definitions (SDD). The idea behind this class is that dependency-graph edges between attributes associated with a production body can go from left to right, but not right to left, thus L-attribute.

L-Attribute grammars are a subset of attribute grammars. They allow the characteristics to be assessed in a single left-to-right traverse of the SDD from depth to the right. As a result, attribute evaluation in L-attributed grammars may be included simply in top-down parsing.

Many computer languages have the letter L attached to them. Narrow compilers are particular sorts of compilers that use some form of L-attributed grammar. S-attributed grammars are a rigorous superset of these. It's used to make code.

We'll go through how to use L-attributed definitions in greater depth in this article because they may be used for a variety of translation purposes. The following techniques traverse a parse tree to do translation:

1. Create a parse tree and annotate it. This approach applies to any noncircular SDD.

2. Create a parse tree, add actions, and execute the actions in a predetermined order.

This method applies to any L-attributed definition.

The following approaches for translation during parsing are discussed in this article:

For each nonterminal, use a recursive-descent parser with one function. The nonterminal A function considers the inherited characteristics of A and returns the synthesized attributes of A.
Using a recursive-descent parser, generate code on the fly.
Combine an SDT with an LL-parser to create an SDT. The characteristics are stored on the parsing stack, and the rules get them from known locations on the stack.
Combining an SDT with an LR-parser is a good idea. This strategy is unexpected since the SDT for an L-attributed SDD usually has actions in the middle of productions. We can't be sure we're in that production until the complete body has been created during an LR parse. However, we'll see that if the underlying grammar is LL, we can always handle both parsing and translation from the bottom up.

Also read About, Specifications of Tokens in Compiler Design and,Lexical Analysis in Compiler Design

Recursive-Descent Parsing

A recursive-descent parser contains a function A for each nonterminal A. As follows, we may turn the parser into a translator:

The inherited properties of nonterminal A are the parameters of function A.
The collection of synthesized characteristics of nonterminal A is the return value of function A.

We must parse and handle attributes in the body of function A:

Choose the product that will be utilized to expand A.
Verify that each terminal is visible on the input when it is needed. We'll assume that no backtracking is required, but the recursive-descent extension is needed. Parsing with backtracking can be accomplished by restoring the input position upon failure.
Preserve the values of all attributes required to compute inherited attributes for nonterminals in the body or synthesized attributes for nonterminals in the head in local variables.
Call functions in the body of the selected products that correspond to nonterminals, passing them the appropriate arguments. We've previously computed these characteristics and saved them in local variables because the underlying SDD is L-attributed.

Example

Grammar: E --> i E'
E' --> + i E' | e

‘e’ is Epsilon.

We will build one program for each variable for the Recursive Descent Parser.

int main()
{
	// The letter E represents the beginning symbol.
	E();

	// If lookahead = $, the string's end is represented.
	if (l == '$')
	printf("ParsingSuccessful");
}

// E's definition, according to the supplied production
E(){
	if (l == 'i') {
 		match('i');
 		E'();
	}
}
// E's definition, according to the supplied production
E'(){
	if (l == '+') {
		match('+');
		match('i');
		E'();
	}//2nd E’s condition
	else if ( l == 'e' )
	{
		match('e');
	}
	return ();
}

// Matchfunction
match(char t)
{
	if (l == t) {
	l = getchar();
}
else
printf("ErrorPrinted");
}

You can also try this code with Online C Compiler

Run Code

On-The-Fly Code Generation

Large strings of code as attribute values are undesirable for various reasons, including the time it may take to copy or transfer long strings. We may alternatively progressively produce pieces of code into an array or output file by performing operations in an SDT in common scenarios like our running code generation example.

The following are the components we'll need to make this strategy work:

1. There is a primary attribute for one or more nonterminals. We shall assume that the primary properties are all string values for convenience.

2. The main characteristics are synthesized.

3. The procedures for evaluating the primary attribute (s) make sure that:

The main attribute is the concatenation of central attributes of nonterminals appearing in the body of the production in question, maybe with non-primary attribute components such as the string label or the values of labels L1 and L2.
The primary qualities of nonterminals are listed in the rule in the same order as they occur in the production body. The main attribute can be constructed by emitting the non-main-attribute elements of the concatenation due to the above conditions. We may rely on the nonterminals in a production body's recursive calls to functions to articulate the value of their primary attribute sequentially.

L-Attributed SDD and LL Parsing

The L-attributed SDD is based on LL grammar and has been transformed into an SDT with actions incorporated into the productions. We can translate the LL parsing by extending the stack to hold activities and specific data items required for attribute evaluation. The data elements are usually duplicates of characteristics.

The parser stack will also contain action records that represent actions to be conducted and synthesize records that carry the synthesized characteristics for nonterminals, in addition to records representing terminals and nonterminals. To control the properties on the stack, we apply the following two principles:

The nonterminal A's inherited properties are stored in the stack record, representing that nonterminal. The code to assess these attributes is commonly represented by an action record directly above the stack record; when L-attributed SDDs are converted to SDTs, the action record is always immediately above A.
The synthesised characteristics for a nonterminal A are stored in a separate synthesize record on the stack, just below the A record.

This technique puts records of various kinds on the parser stack, believing that these different record types can be appropriately maintained as subclasses of the "stackrecord" class. In practice, we may merge numerous records into one, but the concepts are best understood by dividing data for different purposes into separate records.

Pointers to code to be executed are included in action records. Synthesized records may additionally have actions, which generally copy the synthesized attribute(s) onto other records lower down the stack, where the value of that attribute will be required after the synthesized record. Its attributes are pushed off the stack.

Let us take a quick look into LL parsing to observe the requirement to build temporary copies of attributes. A table-driven LL parser imitates a leftmost derivation. If w is the currently matched input, the stack contains a series of grammar symbols, S WA, where S is the start symbol. When the parser expands by a production A ->• BC, it replaces A on top of the stack with BC.

Suppose nonterminal C has an inherited property C.i. With AB C, the inherited attribute C.i may be affected by all B's traits, not only those inherited from A. As a result, we may need to process B completely before evaluating C.i. As a result, in the action record that analyses C.i, we save temporary copies of all the characteristics required to assess C.i. Otherwise, when the parser replaces A on top of the stack with BC, A's inherited properties, and its stack record would vanish.

Because the underlying SDD is L-attributed, we know that when A climbs to the top of the stack, the values of A's inherited attributes will be available. As a result, the values will be ready in time to be transferred into the action record that evaluates C's inherited attributes. Furthermore, there is no difficulty with space for A's synthesized characteristics since the space is in the synthesize-record for A, which stays on the stack below B and C when the parser expands by A -»• BC.

We can duplicate its inherited characteristics for use by C as B is processed (through a record just above B on the stack). Once B is processed, the synthesized record for B can copy its synthesized attributes for use by C if needed. Similarly, A's synthesized attributes may need temporaries to compute their value, which can be transferred to A's synthesize record as B and subsequently C are processed. All of this attribute copying is based on the following principle:

All copying occurs inside the records produced during a single expansion of a nonterminal. As a result, each of these records knows how far down the stack each other record is and may securely put values into those records.
The following example shows how inherited attributes are implemented during LL processing by carefully copying attribute values. Replicate rules, which essentially copy the value of one attribute into another, can be used to provide shortcuts or optimizations.

Bottom-Up Parsing

If every translation can be done from the bottom up, then top-down is possible. We can precisely adapt an LL grammar to compute the same SDD on the new grammar during an LR parse if the grammar has an L-attributed SDD.

There are three components to the "trick":

1. Begin with the SDT described previously, which includes embedded actions before each nonterminal to compute its inherited attributes and a synthesised attribute action after the production.

2. Replace each embedded action with a nonterminal marker in the grammar. Each of these locations is assigned a unique feature, and there is only one product for any marker M, namely M -> e.

3. If the marker nonterminal M substitutes it in some production A an {a} (5, modify the action a and attach an action a' with M -> e.)

Copies any properties of A or symbols of that action a requires as inherited characteristics of M.
Calculates attributes in the same way as a, but converts them to M synthesised attributes.

This modification appears to be prohibited because the action associated with production M —>• e requires typically access to attributes about grammar symbols not present in this production. The activities, however, will be implemented on the LR parsing stack, ensuring that the required characteristics are always available in a known number of locations down the stack.

Example

Assume that in an LL grammar, there is a production A -» BC, and the inherited attribute B.i is computed from the inherited attribute A.i using some formula B.i = f(A.i). That example, the part of an SDT that we are interested in is

A-> {B.i = f{A.i);} BC

We present marker M, which has two attributes: M.i, which is inherited, and M.s, which is synthesised. The first will be an exact replica of A.i, while the second will be B.i. The SDT will be completed.

A -> M B C
M -> {M.i = A.i; M.s = f {M.i);}

It's worth noting that the rule for M doesn't have access to A.i; nonetheless, we'll make sure that every inherited characteristic for a nonterminal like A appears on the stack directly below where the reduction to A will take place later.

As a result, if we decrease e to M, we will discover A.i just below it, from which we may read it. Also, the value of M.s, which is left on the stack with M, is really B.i and is located directly below where the reduction to B will occur later.

Frequently Asked Questions

What is a synthesized attribute?

A synthesized attribute is a non-terminal attribute on the left side of a production. Synthesized attributes represent the information that is transmitted up the parse tree. Only its children can provide value to the attribute.

What is an inherited attribute?

An inherited attribute is a property of a nonterminal on the right side of a production. The attribute can get its value from either its parent or its siblings.

What is L-attributed SDT?

An L-attributed SDT employs both synthesized and inherited attributes with the constraint that the inherited attribute can only inherit values from left siblings.

What is SDD?

SDD stands for Syntax Directed Definition, and it's a type of abstract specification. It's an extension of context-free grammar in which each grammar production X –> a has a set of production rules of the type s = f(b1, b2,......, k), where s is the attribute acquired from function f. A string, integer, type, or memory address can all be used as attributes. Semantic rules are code pieces that are frequently placed towards the conclusion of the production process and surrounded in curly braces ({}).

What are the different techniques to implement L-attributed SDD? Name them.

There are four techniques which are mentioned below:

Translation During Recursive-Descent Parsing
On-The-Fly Code Generation
L-Attributed SDD's and LL Parsing
Bottom-Up Parsing of L-Attributed SDDs

Conclusion

In this article, we have discussed the implementation of L-attributed SDD. We have discussed the various techniques to implement it, such as Translation During Recursive-Descent Parsing, On-The-Fly Code Generation, L-Attributed SDDs and LL Parsing, and Bottom-Up Parsing L-Attributed SDD.