Attribute Grammars/Exercise 10: Expressions and bases - Revision history

Root: /* Solution */

2024-05-02T10:06:30Z

Solution

← Older revision		Revision as of 10:06, 2 May 2024
Line 13:		Line 13:
	The grammar uses only one set of rules for all bases (the default is 10, as shown in the second production for N). The inherited attribute '''b''' contains the base value, while the synthesized attribute '''val''' contains the actual number value.		The grammar uses only one set of rules for all bases (the default is 10, as shown in the second production for N). The inherited attribute '''b''' contains the base value, while the synthesized attribute '''val''' contains the actual number value.

	S<sub>0</sub> -> S<sub>1</sub> '''+''' M { <font color="blue">S<sub>0</sub>.val = S<sub>1</sub>.val + M.val;</font> }		S<sub>0</sub> → S<sub>1</sub> '''+''' M { <font color="blue">S<sub>0</sub>.val = S<sub>1</sub>.val + M.val;</font> }
	S -> M { <font color="blue">S.val = M.val;</font> }		S → M { <font color="blue">S.val = M.val;</font> }

	M<sub>0</sub> -> M<sub>1</sub> '''''' N { <font color="blue">M<sub>0</sub>.val = M<sub>1</sub>.val N.val;</font> }		M<sub>0</sub> → M<sub>1</sub> '''''' N { <font color="blue">M<sub>0</sub>.val = M<sub>1</sub>.val N.val;</font> }
	M -> N { <font color="blue">M.val = N.val;</font> }		M → N { <font color="blue">M.val = N.val;</font> }

	N<sub>0</sub> -> B @ N<sub>1</sub> { <font color="brown">B.b = N<sub>1</sub>.val;</font> <font color="blue">N<sub>0</sub>.val = B.val;</font> }		N<sub>0</sub> → B @ N<sub>1</sub> { <font color="brown">B.b = N<sub>1</sub>.val;</font> <font color="blue">N<sub>0</sub>.val = B.val;</font> }
	N<sub>0</sub> -> N<sub>1</sub> '''DIG''' { <font color="blue">N<sub>0</sub>.val = N<sub>1</sub>.val * 10 + DIG.val;</font> }		N<sub>0</sub> → N<sub>1</sub> '''DIG''' { <font color="blue">N<sub>0</sub>.val = N<sub>1</sub>.val * 10 + DIG.val;</font> }
	N -> '''DIG''' { <font color="blue">N.val = DIG.val;</font> }		N → '''DIG''' { <font color="blue">N.val = DIG.val;</font> }

	B<sub>0</sub> -> B<sub>1</sub> '''DIG''' { <font color="brown">B<sub>1</sub>.b</font> = <font color="brown">B<sub>0</sub>.b</font>; <font color="blue">B<sub>0</sub>.val = B<sub>1</sub>.val * <font color="brown">B<sub>1</sub>.b</font> + DIG.val;</font> }		B<sub>0</sub> → B<sub>1</sub> '''DIG''' { <font color="brown">B<sub>1</sub>.b</font> = <font color="brown">B<sub>0</sub>.b</font>; <font color="blue">B<sub>0</sub>.val = B<sub>1</sub>.val * <font color="brown">B<sub>1</sub>.b</font> + DIG.val;</font> }
	B -> '''DIG''' { <font color="blue">B.val = DIG.val;</font> }		B → '''DIG''' { <font color="blue">B.val = DIG.val;</font> }

	The following is the annotated tree for the string		The following is the annotated tree for the string

Root at 14:25, 6 April 2015

2015-04-06T14:25:00Z

← Older revision		Revision as of 14:25, 6 April 2015
Line 37:		Line 37:
	[[Image:AttrGramEx10Bases1.png]]		[[Image:AttrGramEx10Bases1.png]]

	[[category:~~Compilers~~]]		[[category:Compiladores]]
	[[category:~~Teaching~~]]		[[category:Ensino]]

Root: /* Solution */

2015-03-30T16:52:32Z

Solution

← Older revision		Revision as of 16:52, 30 March 2015
Line 21:		Line 21:
	N<sub>0</sub> -> B @ N<sub>1</sub> { <font color="brown">B.b = N<sub>1</sub>.val;</font> <font color="blue">N<sub>0</sub>.val = B.val;</font> }		N<sub>0</sub> -> B @ N<sub>1</sub> { <font color="brown">B.b = N<sub>1</sub>.val;</font> <font color="blue">N<sub>0</sub>.val = B.val;</font> }
	N<sub>0</sub> -> N<sub>1</sub> '''DIG''' { <font color="blue">N<sub>0</sub>.val = N<sub>1</sub>.val * 10 + DIG.val;</font> }		N<sub>0</sub> -> N<sub>1</sub> '''DIG''' { <font color="blue">N<sub>0</sub>.val = N<sub>1</sub>.val * 10 + DIG.val;</font> }
	N -> '''DIG''' { <font color="blue">R.val = DIG.val;</font> }		N -> '''DIG''' { <font color="blue">N.val = DIG.val;</font> }

	B<sub>0</sub> -> B<sub>1</sub> '''DIG''' { <font color="brown">B<sub>1</sub>.b</font> = <font color="brown">B<sub>0</sub>.b</font>; <font color="blue">B<sub>0</sub>.val = B<sub>1</sub>.val * <font color="brown">B<sub>1</sub>.b</font> + DIG.val;</font> }		B<sub>0</sub> -> B<sub>1</sub> '''DIG''' { <font color="brown">B<sub>1</sub>.b</font> = <font color="brown">B<sub>0</sub>.b</font>; <font color="blue">B<sub>0</sub>.val = B<sub>1</sub>.val * <font color="brown">B<sub>1</sub>.b</font> + DIG.val;</font> }

Root: /* Solution */

2015-03-30T16:51:37Z

Solution

← Older revision		Revision as of 16:51, 30 March 2015
Line 16:		Line 16:
	S -> M { <font color="blue">S.val = M.val;</font> }		S -> M { <font color="blue">S.val = M.val;</font> }

	M<sub>0</sub> -> M<sub>1</sub> '''*''' N { <font color="blue">M<sub>0</sub>.val = M<sub>1</sub>.val + N.val;</font> }		M<sub>0</sub> -> M<sub>1</sub> '''''' N { <font color="blue">M<sub>0</sub>.val = M<sub>1</sub>.val N.val;</font> }
	M -> N { <font color="blue">M.val = N.val;</font> }		M -> N { <font color="blue">M.val = N.val;</font> }

Root: /* Problem (in Portuguese) */

2014-04-03T14:00:31Z

Problem (in Portuguese)

← Older revision		Revision as of 14:00, 3 April 2014
Line 3:		Line 3:
	Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o formato decimal (sequência de dígitos entre 0 e 9, representados pelo elemento lexical '''DIG'''), ou em qualquer base entre 2 e 36 (sequências de dígitos de 0 a 9 e, acima de 10, também contendo as letras de A a Z que forem necessárias para representar todos os valores da base). Quando a base não é decimal, a representação do inteiro é seguida pelo símbolo '''@''' e pelo valor decimal da base.		Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o formato decimal (sequência de dígitos entre 0 e 9, representados pelo elemento lexical '''DIG'''), ou em qualquer base entre 2 e 36 (sequências de dígitos de 0 a 9 e, acima de 10, também contendo as letras de A a Z que forem necessárias para representar todos os valores da base). Quando a base não é decimal, a representação do inteiro é seguida pelo símbolo '''@''' e pelo valor decimal da base.

	O exemplo seguinte tem como resultado 123 + 456 * 789 + B L A H @ 24 = .		O exemplo seguinte tem como resultado 123 + 456 * 789 + B L A H @ 24 = 123 + 359784 + 164417 = 524324.

	1 2 3 + 4 5 6 * 7 8 9 + B L A H @ 2 4		1 2 3 + 4 5 6 * 7 8 9 + B L A H @ 2 4

Root: /* Problem (in Portuguese) */

2014-04-03T13:48:31Z

Problem (in Portuguese)

← Older revision		Revision as of 13:48, 3 April 2014
Line 1:		Line 1:
	== Problem (in Portuguese) ==		== Problem (in Portuguese) ==

	Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o formato decimal (sequência de dígitos entre 0 e 9, representados pelo elemento lexical '''DIG'''), ou em qualquer base entre 2 e 36 (sequências de dígitos de 0 a 9 e, acima de 10, também contendo as letras de A a Z que forem necessárias para representar todos os valores da base). Quando a base não é decimal, a representação do inteiro é ~~precedida pelo valor decimal da base e~~ pelo símbolo '''#'''.		Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o formato decimal (sequência de dígitos entre 0 e 9, representados pelo elemento lexical '''DIG'''), ou em qualquer base entre 2 e 36 (sequências de dígitos de 0 a 9 e, acima de 10, também contendo as letras de A a Z que forem necessárias para representar todos os valores da base). Quando a base não é decimal, a representação do inteiro é seguida pelo símbolo '''@''' e pelo valor decimal da base.

	O exemplo seguinte tem como resultado 123 + 456 * 789 + B L A H @ 24 = .		O exemplo seguinte tem como resultado 123 + 456 * 789 + B L A H @ 24 = .

Root: /* Solution */

2014-04-03T13:45:32Z

Solution

← Older revision		Revision as of 13:45, 3 April 2014
Line 36:		Line 36:

	[[Image:AttrGramEx10Bases1.png]]		[[Image:AttrGramEx10Bases1.png]]

	~~(there is a small bug in the image: 23 should be 17+16=33, as stated in the text)~~

	[[category:Compilers]]		[[category:Compilers]]
	[[category:Teaching]]		[[category:Teaching]]

Root: Created page with "== Problem (in Portuguese) == Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o fo..."

2014-04-03T13:45:21Z

Created page with "== Problem (in Portuguese) == Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o fo..."

New page

== Problem (in Portuguese) ==

Pretende-se criar uma gramática atributiva que some uma sequência de inteiros separados por '''+'''. Os inteiros podem estar codificados sob o formato decimal (sequência de dígitos entre 0 e 9, representados pelo elemento lexical '''DIG'''), ou em qualquer base entre 2 e 36 (sequências de dígitos de 0 a 9 e, acima de 10, também contendo as letras de A a Z que forem necessárias para representar todos os valores da base). Quando a base não é decimal, a representação do inteiro é precedida pelo valor decimal da base e pelo símbolo '''#'''.

O exemplo seguinte tem como resultado 123 + 456 * 789 + B L A H @ 24 = .

1 2 3 + 4 5 6 * 7 8 9 + B L A H @ 2 4

Crie a gramática para realizar a função descrita e construa a árvore semântica anotada para a entrada acima.

== Solution ==

The grammar uses only one set of rules for all bases (the default is 10, as shown in the second production for N). The inherited attribute '''b''' contains the base value, while the synthesized attribute '''val''' contains the actual number value.

S0 -> S1 '''+''' M { S0.val = S1.val + M.val; }
S -> M { S.val = M.val; }

M0 -> M1 '''*''' N { M0.val = M1.val + N.val; }
M -> N { M.val = N.val; }

N0 -> B @ N1 { B.b = N1.val; N0.val = B.val; }
N0 -> N1 '''DIG''' { N0.val = N1.val * 10 + DIG.val; }
N -> '''DIG''' { R.val = DIG.val; }

B0 -> B1 '''DIG''' { B1.b = B0.b; B0.val = B1.val * B1.b + DIG.val; }
B -> '''DIG''' { B.val = DIG.val; }

The following is the annotated tree for the string

1 2 3 + 4 5 6 * 7 8 9 + B L A H @ 2 4

Note that the order of evaluation for the attributes is, first inherited, then synthesized.

Note that, in addition, although this grammar has inherited attibutes, it is not a L-attributed grammar, since there are dependencies from symbols to the right of the value being evaluated.

[[Image:AttrGramEx10Bases1.png]]

(there is a small bug in the image: 23 should be 17+16=33, as stated in the text)

[[category:Compilers]]
[[category:Teaching]]