Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
Aho A.V., Ullman J.D. — The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing
Îáñóäèòå êíèãó íà íàó÷íîì ôîðóìå Íàøëè îïå÷àòêó?
Íàçâàíèå: 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.
ßçûê: Ðóáðèêà: Computer science /Ñòàòóñ ïðåäìåòíîãî óêàçàòåëÿ: Ãîòîâ óêàçàòåëü ñ íîìåðàìè ñòðàíèö ed2k: ed2k stats Ãîä èçäàíèÿ: 1972Êîëè÷åñòâî ñòðàíèö: 542Äîáàâëåíà â êàòàëîã: 10.12.2009Îïåðàöèè: Ïîëîæèòü íà ïîëêó |
Ñêîïèðîâàòü ññûëêó äëÿ ôîðóìà | Ñêîïèðîâàòü ID
Ïðåäìåòíûé óêàçàòåëü
(1,1)-bounded-right-context grammar/language 429—430 448 (2,1)-precedence grammar 426 448 Aanderaa, S.D. 34 Acceptance 96 (see also “Final configuration”) Accessible state 117 125—126 Accumulator 65 Ackley, S.I. 263 Action function 374 392 Adjacency matrix 47—51 Aho, A.V. 102—103 192 251 399 426 Algol 198—199 234 281 489—490 501 Algorithm 27—36 Alphabet 15 Alternates (for a nonterminal) 285 457 Ambiguous grammar 143 163 202—207 281 489—490 Ancestor 39 Antisymmetric relation 10 Arbib, M.A. 138 ARC see “Edge” Arithmetic expression 86 Arithmetic progression 124 209 Assembler 59 74 Assembly language 65—70 assignment statement 65—70 Asymmetric relation 9 atom 1—2 Augmented grammar 372—373 427—428 Automaton see “Recognizer” “Transducer” Axiom 19—20 Backtrack parsing 281—314 456—500 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 62—63 74 255 Boolean algebra 23—24 129 Booth, T.L. 138 Border (of a sentential form) 334 369 Borodin, A. 36 Bottom-up parsing 178—184 268—271 301—307 485—500 “Floyd “LR(k) “Precedence Bounded context grammar/language 450—452 Bounded-right-context grammar/language 427—435 448 451—452 BRC see “Bounded-right context” Brooker, R.A. 77 313 Brzozowski, J.A. 124 138 Canonical collection of sets of valid items 389—391 Canonical LR(k) parser 393—396 Canonical set of LR(k) tables 393—394 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 238—243 251 Cheatham, T.E. 58 77 280 314 Chomsky grammar 29 (see also “Grammar”) Chomsky hierarchy 92 Chomsky normal form 150—153 243 276—277 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 17—18 197 Closure of a set of valid items 386 Closure, reflexive and transitive 8—9 Closure, transitive 8—9 47—50 52 CNF see “Chomsky normal form” Cocke — Younger — Kasami algorithm 281 314—320 Cocke, J. 76 332 Code Generation 59 65—70 72 74 Code optimization 59 70—72 Cohen, R.S. 500 Colmerauer grammar 492 497—500 Colmerauer precedence relations 490—500 Colmerauer, A. 500 Commutative law 71 Compiler 53—77 (see also “Bookkeeping” “Code “Code “Error “Lexical “Parsing”) Compiler-compiler 77 Complementation 4 189—190 197 208 484 Completely specified finite automaton 117 Composition (of relations) 13 250 Computational complexity 27—28 208 210 297—300 316—320 326—328 356 395—396 473—476 Concatenation 15 17 197 208—210 Configuration 34 95 113—114 168—169 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 91—93 97 99 101 208 399 Context-sensitive grammar/language 91—93 97 99 101 208 399 Continuing pushdown automaton 188 Conway, R.W. 77 Cook, S.A. 34 192 Correspondence problem see “Post’s 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) 140—141 CYCLE 39 Cycle-free grammar 150 280 302—303 307 D-chart 79—82 Dag 39—40 42—45 116 Dangling else 202—204 Davis, M. 36 de Morgan’s laws 12 De Remer, F.L. 399 512 Decidable problem see “Problem” Defining equations (for context-free languages) 159—163 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 226—227 (see also “Finite transducer”) Deterministic pushdown automaton 184—192 201—202 208—210 251 344 398 446 448 466—469 Deterministic pushdown transducer 229 251 271—275 341 395 443 446 Deterministic recognizer 95 (see also “Recognizer” “Deterministic “Deterministic “Deterministic Deterministic two-stack parser 488 492—493 500 Dewar, R.B.K. 77 Diagnostics see “Error correction” Difference (of sets) 4 Dijkstra, E.W. 79 Direct lexical analysis 61—62 258—261 Directed acyclic graph see “Dag” Directed graph see “Graph” Disjoint sets 4 Distinguishable states (of a finite automaton) 124—128 Domain 6 10 Domolki’s algorithm 312—313 452 DPDA see “Deterministic pushdown automaton” DPDT see “Deterministic pushdown transducer” Dyck language 209 e-free first (EFF) 381—382 392 398 e-free grammar 147—149 280 302—303 397 e-move 168 190 e-production 92 147—149 362 Earley L 332 Earley’s algorithm 73 281 320—331 397—398 EDGE 37 Eickel, J. 455 Eight queens problem 309 Elementary operation 317 319 326 395 Emptiness problem 130—132 144—145 483 Empty set 2 Empty string 15 Endmarker 94 271 341 404 469 484 Engeler, E. 58 English, structure of 55—56 78 Equivalence class see “Equivalence relation” Equivalence problem 130—132 201 237 362 Equivalence relation 6—7 12—13 126 133—134 Error correction 59 72—74 77 367 394 399 426 Euclid’s algorithm 26—27 36 Evans, A. 455 Evey, R.J. 166 192 Extended precedence grammar 410—415 424—425 429 451 Extended pushdown automaton 173—175 185—186 Extended pushdown transducer 269 Extended regular expression 253—258 extensible language 58 501—504 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 112—121 124—128 255—261 397 Finite control 95 443 Finite set 11 14 Finite transducer 223—227 235 237—240 242 250 252 254—255 258 first 300 335—336 357—359 Fischer, M.J. 102 426 Fischer, P.C. 36 Flow chart 79—82 Floyd — Evans productions 443—448 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 469—485 Gentleman, W.M. 61 Gill, A. 138 Ginsburg, S. 102—103 338 166 211 237 Ginzburg, A. 138 GNF see “Greibach normal form” Gotlieb, C.C. 314 goto 386—390 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 37—52 Graph grammar see “Web grammar” Gray, J.N. 192 280 455 500 Greek letters 214 Greibach normal form 153—162 243 280 362 Greibach, S.A. 102—103 166 211 Gries, D. 76—77 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 282—285 Handle (of a right sentential form) 179—180 377 379—380 403—404 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 17—18 197 207 209 213 Hopcroft, J.E. 36 102—103 138 192 211 368 399 Hopgood, F.R.A. 76 455 Horning, J.J. 76—77 450 465 Huffman, D.A. 138 Ibarra, O. 192 Ichbiah, J.D. 426 Identifier 60—63 252 254 In-degree 39 Inaccessible state see “Accessible state” Inaccessible symbol (of a context-free grammar) 145—147 Inclusion (of sets) 3 208 Index (of an equivalence relation) 7 Indexed grammar 100—101 Indirect lexical analysis 61—62 254—258 Indistinguishable states see “Distinguishable states” Induction see “Proof by induction” Infinite set 11 14 Ingerman, P.Z. 77 Inherent ambiguity 205—207 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 94—96 Input symbol 113 168 218 224 Input tape 93—96 Intermediate (of an indexed grammar) 100 Intermediate code 59 65—70 Interpreter 55 Intersection 4 197 201 208 484 Inverse (of a relation) 6 10—11 Inverse Unite transducer mapping 227 Irland, M.I. 36 Irons, E.T. 77 237 314 455 Irreflexive relation 9 Item (Earley’s algorithm) 320 331 397—398 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 16—17 83—84 86 96 114 169 “Grammar”) LBA see “Linear bounded automaton” LC(k) grammar/language 362—367 Leavenworth, B.M. 58 501 Lee, E.S. 450 Lee, J.A.N. 76 Left cover 275—277 280 307 Left factoring 345
Ðåêëàìà
|
|
Î ïðîåêòå