Knowledge in Computer Architecture
Software Productivity Tool
Software Productivity ToolsDataflow techniques developed for optimizing code are also useful for finding errors. Here correctness is not an absolute requirement, a good thing since finding all errors in undecidable.Type CheckingTechniques developed to check for type correctness (we will see some of these) can be extended to find other errors such as using an uninitialized variable.Bounds CheckingAs mentioned above optimizations have been developed to eliminate unnecessary bounds checking for languages like Ada and Java that perform the checks automatically. Similar techniques can help find potential buffer overflow errors that can be a serious security threat.Memory-Management ToolsLanguages (e.g., Java) with garbage collection cannot have memory leaks (failure to free no longer accessible memory). Compilation techniques can help to find these leaks in languages like C that do not have garbage collection.
Amrita Bagchi
Syntax Analysis in Compiler design
IntroductionWe will be looking at the front end, i.e., the analysis portion of a compiler.The syntax describes the form of a program in a given language, while the semanticsdescribes the meaning of that program. We will use the standard context-free grammaror BNF (Backus-Naur Form) to describe the syntaxWe will learn syntax-directed translation, where the grammar does more than specify the syntax. We augment the grammar with attributes and use this to guide the entire front end.The front end discussed in this chapter has as source language infix expressions consisting of digits, +, and -. The target language is postfix expressions with the same components. The compiler will convert7+4-5 to 74+5-.Actually, our simple compiler will handle a few other operators as well.We will tokenize the input (i.e., write a scanner), model the syntax of the source, and let this syntax direct the translation all the way to three-address code, our intermediate language.Syntax DefinitionDefinition of GrammarsA context-free grammar (CFG) consists ofA set of terminal tokens.A set of nonterminals.A set of productions (rules for transforming nonterminals).A specific nonterminal designated as start symbol.Example: Terminals: 0 1 2 3 4 5 6 7 8 9 + - Nonterminals: list digit Productions: list → list + digit list → list - digit list → digit digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Start symbol: list If no start symbol is specifically designated, the LHS of the first production is the start symbol.DerivationsWatch how we can generate the input 7+4-5 starting with the start symbol, applying productions, and stopping when no productions are possible (we have only terminals). list → list - digit → list - 5 → list + digit - 5 → list + 4 - 5 → digit + 4 - 5 → 7 + 4 - 5 This process of applying productions, starting with the start symbol and ending when only terminals are present is called aderivation and we say that the final string has been derived from the initial string (in this case the start symbol).The set of all strings derivable from the start symbol is the language generated by the CFGIt is important that you see that this context-free grammar generates precisely the set of infix expressions with single digits as operands (so 25 is not allowed) and + and - as operators.The way you get different final expressions is that you make different choices of which production to apply. There are 3 productions you can apply to list and 10 you can apply to digit.The result cannot have blanks since blank is not a terminal.The empty string is not possible since, starting from list, we cannot get to the empty string. If we wanted to include the empty string, we would add the productionlist → εThe idea is that the input language to the compiler is approximately the language generated by the grammar. It is approximate since I have ignored the scanner.Given a grammar, parsing a string consists of determining if the string is in the language generated by the grammar. If it is in the language, parsing produces a derivation. If it is not, parsing reports an error.The opposite of derivation is reduction, that is, the LHS of a production, produces the RHS (a derivation) and the RHS is reduced by the production to the LHS.
Operators associativity and precedence
Associativity of operatorsOur grammar gives left associativity. That is, if you traverse the parse tree in postorder and perform the indicated arithmetic you will evaluate the string left to right. Thus 8-8-8 would evaluate to -8. If you wished to generate right associativity (normally exponentiation is right associative, so 2**3**2 gives 512 not 64), you would change the first two productions to list → digit + list list → digit - list Produce in class the parse tree for 7+4-5 with this new grammar.Precedence of operatorsWe normally want * to have higher precedence than +. We do this by using an additional nonterminal to indicate the items that have been multiplied. The example below gives the four basic arithmetic operations their normal precedence unless overridden by parentheses. Redundant parentheses are permitted. Equal precedence operations are performed left to right. expr → expr + term | expr - term | term term → term * factor | term / factor | factor factor → digit | ( expr ) digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 We use | to indicate that a nonterminal has multiple possible right hand side. So A → B | C is simply shorthand for A → B A → C Do the examples 1+2/3-4*5 and (1+2)/3-4*5 on the board.Note how the precedence is enforced by the grammar; slick!StatementsKeywords are very helpful for distinguishing statements from one another.stmt → id := expr | if expr then stmt | if expr then stmt else stmt | while expr do stmt | begin opt-stmts end opt-stmts → stmt-list | ε stmt-list → stmt-list ; stmt | stmt Remarks:opt-stmts stands for optional statements. The begin-end block can be empty in some languages.The ε (epsilon) stands for the empty string.The use of epsilon productions will add complications.Some languages do not permit empty blocks For example, Ada has a nullstatement, which does nothing when executed, for this purpose.The above grammar is ambiguous!The notorious “dangling else” problem.How do you parse if x then if y then z=1 else z=2?
Removal of Sludge and commissioning of the septic tank
Removal of Sludge and commissioning of the septic tank
Syed Sadique Hussain
Components of the bridge
Components of the bridge
Brain computer interface
Brain computer interface
Aptitude Mantra
IP spoofing
IP spoofing
Fedora Os
Fedora Os computing
Family organic chemistry
Family organic chemistry
Brain computer interface
Brain computer interface
Introduction to Computer Organisation
Types of Computers, Functional Units, Basic Operational Concept, Bus Structures, Software, Performance, Processor Clock, Basic Performance Equation, Pipelining and Superscaling Operation, Clock Ratio, Instruction Set: CISC and RISC, Compiler, Performance Measurement, Multi-Processors and Multi-COmputers, Data Representation, Number Systems, Fixed Point Representation, Floating Point Representation.
Soumya Somayajula
Sunny