# Tag Info

## Hot answers tagged attribute-grammars

3

You are using the terms in a weird way. A grammar can be circular or non-circular. Since FULLY testing this property is EXPTIME, one wants a simpler (easier to test) property. This is where strong NON-circularity comes in. In strong non-circularity, you basically combine the dependencies of all possible sub-trees, even for combinations that can't appear ...

3

I've usually seen it expressed as something like: forExpression ::= for ( <declExpression> <expression>; <expression> ) <blockStatement> blockStatement ::= <statement> | { <statementlist> } statement ::= <declExpression> | <forExpression> | <ifExpression> | ... <declExpression> includes the ...

3

Using a top-down translation scheme, we can implement any $LL$-attributed definition based on $LL(1)$ grammar. Using a bottom-up translation scheme, we can also implement any $LL$-attributed definition based on $LL(1)$ grammar (each $LL(1)$ grammar is also an $LR(1)$ grammar). Using bottom-up translation scheme, we implement $LR$ grammar actually but since $... 3 Attribute grammars are a conceptual tool. You are mixing this up with implementation details. There are many parser generators around (check for example the Wikipedia pages on compiler compilers and comparison of parser generators). They all implement some flavor of attribute grammar, in actual use you aren't interested in a parse tree or a derivation. The ... 3 The computer is using the rules in the left-hand column of your table. This amounts to a bottom up approach: to compute the value of a node you first compute (recursively) the values of all its children, and then you use the given rule to compute the value of the node itself. 2 In attribute grammars, you have variables attached to the symbols in the parse-tree which can take values. Equations attached to the rules specify how these values are propagated through the tree. For that purpose, different occurences of a non-terminal in the same rule are distinguished by subscripts, so as to distinguish the variables attached to them. ... 2 In an attribute grammar one assigns values to the nonterminals of the grammar. This is to help evaluating parts of a grammar that are not context-free. One of the simple types is inherited attributes, these are assigned bottom-up in the derivation tree. The indexes$S_0$and$S_1$are used here to distingish different occurrences of the nonterminal$S$in ... 2 This is plainly wrong. The set of all Java programs that always terminate is not recursively enumerable (essentially the halting problem), and so can't be generated by any grammar. Ambiguous context free grammars are hard to parse efficiently, compiler writers prefer unambiguous grammars (or use tricks in the parser to bypass ambiguities). If the underlying ... 1 You don't evaluate nodes in an attribute grammar. You evaluate attributes. At a given node there may be zero or more attributes to evaluate, and they don't necessarily get evaluated on the same visit to the node. So the evaluator may indeed need to visit nodes multiple times. This theoretical structure corresponds to compilers which do multiple passes over ... 1 But in the above excerpt,$A.in$for the nodes$A$of the parse is not defined in terms of attributes at the parent of siblings. Yes, it is. The parent of$A\to a$is$S \to A_1 A_2$.$S$has two children, both of which are instances of$A$. And the rule for$S \to A_1 A_2$assigns values to the inherited attributes of both children. That's precisely what ... 1 L-attributed definitions are definition whose attributes can be evaluated in depth-first order (as they say in the first sentence). The statement "L-attributed definitions include all syntax-directed definitions based on LL(1) grammars" is perhaps a bit subtle. It's not saying that the two sets of definitions are the same; rather, that syntax-... 1 It's not a claim; it's a definition. In mathematics, we can define things however we want. [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 ... 1 The semantic rules of the attribute grammar "compute" the value of the expression to the left in terms of the values of the expressions to the right. With a grammar for regular expressions as you propose this is straightforward, but precisely because of that this can be confusing. For instance the meaning of the rule$S_0\to S_1 S_2\$ is ...

1

Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" won't work so well. In a sense, the regular expression is a compact description of the language. What other kind of description do you expect to construct? It is rather easy to construct regular ...

1

LL Means Left read and Left derived and LR is Left read and Right derived the left and right part generally makes the difference between how the parser is written and if it top down or bottom up parsing. The dragon book should be your go-to reference for anything related to parsers and parsing techniques.

1

As I understand it, it's basically a variable of sorts to work out what has and hasn't been backed up. So when a backup is taken, the archive attribute will be set to '0', now as a user modifies files, their archive attribute will be set to '1' meaning when the next backup is taken, rather than backing up every file again, the files with the archive ...

1

I do not know any specific implementations, but here are two ideas a annotate nodes w.r.t an attribute grammars: A recursive algorithm can evaluate top-down and bottom-up rules in two passes over the tree. You may want to implement it using the visitor pattern Use the iterator pattern. Note that the order of iteration is crucial -- decide between pre-, ...

1

First grammars describes languages. Formally context free, context sensitive and ambiguous qualify grammars and not languages (I've never seen ambiguous used to describe a language, I've seen context free and context sensitive used to describe languages with the meaning "there is at least one context free/sensitive grammar describing the language"). ...

1

The sum function of your example itself is already stepping out of the strict scope of the grammar. Or you'd have to to explicitly include all the machinery used in your attributed grammar into it, in which case nothing forbids adding (some formalization of) SQL and a database to it.

Only top voted, non community-wiki answers of a minimum length are eligible