Ex Libris                        Wanted                           
blank

       
blank

blank
blank
blank
blank
Aho A.V., Ullman J.D. The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing
Aho A.V., Ullman J.D.  The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing







?
Ctrl+Enter


: The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing

: Aho A.V., Ullman J.D.

:

This book is intended for a one or two semester course in compiling theory at the senior or graduate level. It is a theoretically oriented treatment of a practical subject. Our motivation for making it so is threefold.

In an area as rapidly changing as Computer Science, sound pedagogy demands that courses emphasize ideas, rather than implementation details. It is our hope that the algorithms and concepts presented in this book will survive the next generation of computers and programming languages, and that at least some of them will be applicable to fields other than compiler writing.

Compiler writing has progressed to the point where many portions of a compiler can be isolated and subjected to design optimization. It is important that appropriate mathematical tools be available to the person attempting this optimization.

Some of the most useful and most efficient compiler algorithms, e.g. LR(k) parsing, require a good deal of mathematical background for full understanding. We expect, therefore, that a good theoretical background will become essential for the compiler designer.

While we have not omitted difficult theorems that are relevant to compiling, we have tried to make the book as readable as possible. Numerous examples are given, each based on a small grammar, rather than on the large grammars encountered in practice. It is hoped that these examples are sufficient to illustrate the basic ideas, even in cases where the theoretical developments are difficult to follow in isolation.


: en

: Computer science/

:

ed2k: ed2k stats

: 1972

: 542

: 10.12.2009

: | | ID
blank
(1,1)-bounded-right-context grammar/language      429430 448
(2,1)-precedence grammar      426 448
Aanderaa, S.D.      34
Acceptance      96 (see also Final configuration)
Accessible state      117 125126
Accumulator      65
Ackley, S.I.      263
Action function      374 392
Adjacency matrix      4751
Aho, A.V.      102103 192 251 399 426
Algol      198199 234 281 489490 501
Algorithm      2736
Alphabet      15
Alternates (for a nonterminal)      285 457
Ambiguous grammar      143 163 202207 281 489490
Ancestor      39
Antisymmetric relation      10
Arbib, M.A.      138
ARC      see Edge
Arithmetic expression      86
Arithmetic progression      124 209
Assembler      59 74
Assembly language      6570
assignment statement      6570
Asymmetric relation      9
atom      12
Augmented grammar      372373 427428
Automaton      see Recognizer Transducer
Axiom      1920
Backtrack parsing      281314 456500
Backus Naur form      58 (see also Context-free grammar)
Backus, J.W.      76
Backwards determinism      see Unique invertibility
Bar-Hillel, Y.      82 102 211
Barnett, M.P.      237
Bauer, F.L.      455
Bauer, H.      426
Becker, S.      426
Berge, C.      52
Bijection      10
Birman, A.      485
Blaitner, M.      211
BNF      see Backus Naur form
Bobrow, D.G.      82
Book, R.V.      103 211
bookkeeping      59 6263 74 255
Boolean algebra      2324 129
Booth, T.L.      138
Border (of a sentential form)      334 369
Borodin, A.      36
Bottom-up parsing      178184 268271 301307 485500 Floyd LR(k) Precedence
Bounded context grammar/language      450452
Bounded-right-context grammar/language      427435 448 451452
BRC      see Bounded-right context
Brooker, R.A.      77 313
Brzozowski, J.A.      124 138
Canonical collection of sets of valid items      389391
Canonical LR(k) parser      393396
Canonical set of LR(k) tables      393394
Cantor, D.G.      211
Cardinality (of a set)      11 14
Cartesian product      5
Catalan number      165
CFG      see Context-free grammar
CFL      see Context-free language
Characteristic function      34
Characterizing language      238243 251
Cheatham, T.E.      58 77 280 314
Chomsky grammar      29 (see also Grammar)
Chomsky hierarchy      92
Chomsky normal form      150153 243 276277 280 314 362
Chomsky, N.      29 58 82 102 124 166 192 211
Christensen, C.      58
Church Turing thesis      29
Church, A.      25 29
Circuit      see Cycle
Closed portion (of a sentential form)      334 369
Closure of a language      1718 197
Closure of a set of valid items      386
Closure, reflexive and transitive      89
Closure, transitive      89 4750 52
CNF      see Chomsky normal form
Cocke Younger Kasami algorithm      281 314320
Cocke, J.      76 332
Code Generation      59 6570 72 74
Code optimization      59 7072
Cohen, R.S.      500
Colmerauer grammar      492 497500
Colmerauer precedence relations      490500
Colmerauer, A.      500
Commutative law      71
Compiler      5377 (see also Bookkeeping Code Code Error Lexical Parsing)
Compiler-compiler      77
Complementation      4 189190 197 208 484
Completely specified finite automaton      117
Composition (of relations)      13 250
Computational complexity      2728 208 210 297300 316320 326328 356 395396 473476
Concatenation      15 17 197 208210
Configuration      34 95 113114 168169 224 228 290 303 338 477 488
Conflict, precedence      see Precedence conflict
Congruence relation      134
Consistent set of items      391
Constant      254
Context-free grammar/language      9193 97 99 101 208 399
Context-sensitive grammar/language      9193 97 99 101 208 399
Continuing pushdown automaton      188
Conway, R.W.      77
Cook, S.A.      34 192
Correspondence problem      see Posts correspondence problem
Countable set      11 14
Cover, grammatical      see Left cover Right
CSG      see Context-sensitive grammar
CSL      see Context-sensitive language
Culik, K.H.      368 500
Cut (of a parse tree)      140141
CYCLE      39
Cycle-free grammar      150 280 302303 307
D-chart      7982
Dag      3940 4245 116
Dangling else      202204
Davis, M.      36
de Morgans laws      12
De Remer, F.L.      399 512
Decidable problem      see Problem
Defining equations (for context-free languages)      159163
Denning, P.J.      426
Derivation      86 98
Derivation tree      see Parse tree
Derivative (of a regular expression)      136
Descendant      39
Deterministic finite automaton      116 255
Deterministic finite transducer      226227 (see also Finite transducer)
Deterministic pushdown automaton      184192 201202 208210 251 344 398 446 448 466469
Deterministic pushdown transducer      229 251 271275 341 395 443 446
Deterministic recognizer      95 (see also Recognizer Deterministic Deterministic Deterministic
Deterministic two-stack parser      488 492493 500
Dewar, R.B.K.      77
Diagnostics      see Error correction
Difference (of sets)      4
Dijkstra, E.W.      79
Direct lexical analysis      6162 258261
Directed acyclic graph      see Dag
Directed graph      see Graph
Disjoint sets      4
Distinguishable states (of a finite automaton)      124128
Domain      6 10
Domolkis algorithm      312313 452
DPDA      see Deterministic pushdown automaton
DPDT      see Deterministic pushdown transducer
Dyck language      209
e-free first (EFF)      381382 392 398
e-free grammar      147149 280 302303 397
e-move      168 190
e-production      92 147149 362
Earley      L 332
Earleys algorithm      73 281 320331 397398
EDGE      37
Eickel, J.      455
Eight queens problem      309
Elementary operation      317 319 326 395
Emptiness problem      130132 144145 483
Empty set      2
Empty string      15
Endmarker      94 271 341 404 469 484
Engeler, E.      58
English, structure of      5556 78
Equivalence class      see Equivalence relation
Equivalence problem      130132 201 237 362
Equivalence relation      67 1213 126 133134
Error correction      59 7274 77 367 394 399 426
Euclids algorithm      2627 36
Evans, A.      455
Evey, R.J.      166 192
Extended precedence grammar      410415 424425 429 451
Extended pushdown automaton      173175 185186
Extended pushdown transducer      269
Extended regular expression      253258
extensible language      58 501504
Feldman, J.A.      77 455
Fetch function (of a recognizer)      94
FIN      135 207
Final configuration      95 113 169 175 224 228 339
Final state      113 168 224
Finite ambiguity      332
Finite automaton      112121 124128 255261 397
Finite control      95 443
Finite set      11 14
Finite transducer      223227 235 237240 242 250 252 254255 258
first      300 335336 357359
Fischer, M.J.      102 426
Fischer, P.C.      36
Flow chart      7982
Floyd Evans productions      443448 452
Floyd, R.W.      52 77 166 211 314 426 455
FOLLOW      343 425
Formal Semantic Language      455
FORTRAN      252 501
Freeman, D.N.      77 263
Frontier (of a parse tree)      140
Function      30 14
Futrelle, R.P.      237
Galler, B.A.      58
Generalized top-down parsing language      469485
Gentleman, W.M.      61
Gill, A.      138
Ginsburg, S.      102103 338 166 211 237
Ginzburg, A.      138
GNF      see Greibach normal form
Gotlieb, C.C.      314
goto      386390 392
Goto function      374 392
Graham, R.M.      455
Graham, S.L.      426
Grammar      85 (see also Bounded-right-context grammar Colmerauer Context-free Context-sensitive Indexed LC(k) LL(k) LR(k) Operator Precedence Right Unrestricted Web
Graph      3752
Graph grammar      see Web grammar
Gray, J.N.      192 280 455 500
Greek letters      214
Greibach normal form      153162 243 280 362
Greibach, S.A.      102103 166 211
Gries, D.      7677
Griffiths, T.V.      314
Griswold, R.E.      505
Gross, M.      211
GTDPL      see Generalized top-down parsing language
Haines, L.H.      103
Halmos, P.R.      3 25
HALTING      see Recursive Algorithm
Halting problem      35
Halting pushdown automaton      282285
Handle (of a right sentential form)      179180 377 379380 403404 486
Harary, E.      52
Harrison, M.A.      138 192 280 455 500
Hartmanis, J.      36 192
Hash table      63
Haskell, R.      280
Hays, D.G.      332
Hext, J.B.      314
Hocbsprung, R.R.      77
Homomorphism      1718 197 207 209 213
Hopcroft, J.E.      36 102103 138 192 211 368 399
Hopgood, F.R.A.      76 455
Horning, J.J.      7677 450 465
Huffman, D.A.      138
Ibarra, O.      192
Ichbiah, J.D.      426
Identifier      6063 252 254
In-degree      39
Inaccessible state      see Accessible state
Inaccessible symbol (of a context-free grammar)      145147
Inclusion (of sets)      3 208
Index (of an equivalence relation)      7
Indexed grammar      100101
Indirect lexical analysis      6162 254258
Indistinguishable states      see Distinguishable states
Induction      see Proof by induction
Infinite set      11 14
Ingerman, P.Z.      77
Inherent ambiguity      205207 209
INIT      135 207
Initial configuration      95 113 169
Initial state      113 168 224
Initial symbol (of a pushdown automaton)      168
Injection      10
Input head      9496
Input symbol      113 168 218 224
Input tape      9396
Intermediate (of an indexed grammar)      100
Intermediate code      59 6570
Interpreter      55
Intersection      4 197 201 208 484
Inverse (of a relation)      6 1011
Inverse Unite transducer mapping      227
Irland, M.I.      36
Irons, E.T.      77 237 314 455
Irreflexive relation      9
Item (Earleys algorithm)      320 331 397398
Item (LR(k))      381 (see also Valid Item)
Johnson, W.L.      263
k-predictive parsing algorithm      see Predictive parsing algorithm
Karneda, T.      138
Kasami, T.      332
Keyword      59 259
Kleene, S.C.      36 124
Knuth, D.E.      36 58 368 399 485
Korenjak, A.J.      368 399
Kosaraju, S.R.      138
Kuno, S.      313
Kurki-Suonio, R.      368
Labeled graph      38 42
LaLonde, W.R.      450
Lambda calculus      29
Language      1617 8384 86 96 114 169 Grammar)
LBA      see Linear bounded automaton
LC(k) grammar/language      362367
Leavenworth, B.M.      58 501
Lee, E.S.      450
Lee, J.A.N.      76
Left cover      275277 280 307
Left factoring      345
1 2 3
blank
blank
blank
HR
@Mail.ru
       © , 2004-2019
   | Valid HTML 4.01! | Valid CSS!