Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
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
Ïðåäìåòíûé óêàçàòåëü
Left linear grammar 122 Left parsable grammar 271—275 341 Left parse see “Leftmost derivation” “Top-down Left parse language 273 277 Left parser 266—268 Left recursion 484 (see also “Left recursive grammar”) Left sentential form 143 Left-bracketed representation (for trees) 46 Left-corner parse 278—280 310—312 362—367 Left-corner parser 310—312 Left-recursive grammar 153—158 287—288 294—298 344—345 Leftmost derivation 142—143 204 318—320 Leinius, R.P. 399 426 Length of a derivation 86 Length of a string 16 Lentin, A. 211 Lewis, P.M. II 192 237 368 Lexical analysis 59—63 72—74 251—264 Lexicographic order 13 Linear bounded automaton 100 (see also “Context-sensitive grammar”) Linear grammar/language 165—170 207—208 237 Linear order 10 13—14 43—45 Linear set 209—210 LL(1) grammar 342—349 483 LL(k) grammar/language 73 268 333—368 397—398 448 452 LL(k) table 349—351 354—355 Loeckx, J. 455 Logic 19—25 Logical connective 21—25 Lookahead 300 306 331 334—336 363 371 Looping (in a pushdown automaton) 186—189 LR(1) grammar 410 448—450 LR(k) grammar/language 73 271 369 371—399 402 424 428 430 448 LR(k) table 374—376 392—394 398 Lucas, P. 58 Lukasiewicz, J. 214 Mapping see “Function” Marked closure 210 Marked concatenation 210 Marked union 210 Markov algorithm 29 Markov, A.A. 29 MAX 135 Maxwell, W.L. 77 McCarthy, J. 77 McClure, R.M. 77 485 McCullough, W.S. 103 McKeemaa, W.M. 76—77 426 455 Mcllroy, M.D. 58 61 McNaughton, R. 124 Membership (relation on sets) 1 Membership problem 130—132 Memory (of a recognizor) 93—96 Mendelson, E. 25 META 485 Miller, G.A. 124 Miller, W.F. 82 MIN 135 207 209 Minimal fixed point 108—110 121—123 160—161 Minsky, M. 29 36 102 138 Mixed-strategy precedence grammar 435 437—439 448 452 Montanari, U.G. 82 Moore, E.F. 103 138 Morgan, H.L. 77 263 Morris, D. 77 313 Morse, S.P. 426 Moulton, P.G. 77 Move (of a recognizer) 95 Msp see “Mixed strategy precedence” Muller, M.E. 77 Munro, I. 52 Natural languages 78 281 Naur, P. 58 Next move function 168 224 Node 37 Non-left-recursive grammar see “Left recursive grammar” Nondeterministic algorithm 285 308—310 Nondeterministic finite automaton 117 (see also “Finite automaton”) Nondeterministic FORTRAN 308—310 Nondeterministic recognizer 95 (see also “Recognizer”) Nonterminal 85 100 218 458 Nose colds in hogs 78 Object code 59 Oettinger, A. 192 313 Ogden, W. 211 Ogden’s lemma 192—196 One-turn pushdown automaton 207—208 One-way recognizer 94 Open portion (of a sentential form) 334 369 Operator grammar/language 165 438 Operator precedence grammar/language 439—443 448—450 452 Order (of a syntax-directed translation) 243—251 Ordered dag 42 (see also “Dag”) Ordered graph 41—42 Ordered tree 42—44 (see also “Tree”) Ore, O. 52 Out degree 39 Output symbol 218 224 Painter, J.A. 77 Pair, C. 426 PAL 512—517 Parikh, R.J. 211 Parikh’s theorem 209—211 Parse lists 321 Parse table 316 339 345—346 348 351—356 364—365 374 Parse tree 139—143 179—180 220—222 273 379 464—466 Parsing 56 59 63—65 72—74 263—280 “Shift-reduce “Top-down Parsing action function see “Action function” Parsing machine 477—482 484 Partial acceptance failure (of a TDPL or GTDPL program) 484 Partial correspondence problem 36 Partial function 10 Partial left parse 293—296 Partial order 9—10 13—15 43—45 Partial recursive function see “Recursive function” Partial right parse 306 Path 39 51 Pattern recognition 79—82 Paul, M. 455 Paull, M.C. 166 Pavlidis, T. 82 PDA see “Pushdown automaton” Perils, A.J. 58 Perles, M. 211 Petrick, S.R. 314 Pfaltz, J.L. 82 phrase 486 Pitts, E. 103 PL/I 501 PL360 507—511 Poage, J.F. 505 Polish notation see “Prefix expression” “Postfix Polonsky, I.P. 505 Porter, J.H. 263 Position (in a string) 193 Post system 29 Post, E, L. 29 36 Postfix expression 214—215 217—218 229 512 Postorder (of a tree) 43 Post’s correspondence problem 32—36 199—201 POT see “Pushdown transducer” Power set 5 12 Prather, R.E. 138 Precedence (of operators) 65 233—234 Precedence conflict 419—420 Precedence grammar/language 399—400 403—404 “Mixed-strategy “Operator “Simple “X-canonical “Weak Predecessor 37 Predicate 2 Predictive parsing algorithm 338—348 351—356 Prefix expression 214—215 229 236 prefix property 17 19 209 Preorder (of a tree) 43 Problem 29—36 Procedure 25—36 Product of languages 17 (see also “Concatenation”) Product of relations 7 Production 85 100 Production language 443 proof 19—21 43 Proof by induction 20—21 43 Proper grammar 150 Propositional calculus 22—23 35 Pumping lemma for context-free languages 195—196 (see also “Ogden’s lemma”) Pumping lemma for regular sets 128—129 Pushdown automaton 167—192 201 282 Pushdown symbol 168 Pushdown transducer 227—233 237 265—268 282—285 Question see “Problem” Rabin, M.O. 103 124 Randell, B. 76 RANGE 6 10 Recognizer 93—96 103 “Linear “Parsing “Pushdown “Turing “Two-stack Recursive function 28 Recursive grammar 153 163 Recursive set 28 34 99 Recursively enumerable set 28 34 92 97 500 Reduced finite automaton 125—128 Reflexive relation 6 Reflexive-transitive closure see “Closure” “Reflexive Regular definition 253—254 Regular expression 104—110 121—123 Regular expression equations 105—112 121—123 Regular grammar 122 499 Regular set 103—138 191 197 208—210 227 235 238—240 424 Regular translation see “Finite transducer” Relation 5—15 Reversal 16 121 129—130 397 500 Reynolds, J.C. 77 280 313 Rice, H.G. 166 Right cover 275—277 280 307 Right invariant equivalence relation 133—134 Right linear grammar 91—92 99 110—112 118—121 201 Right linear syntax-directed translation scheme 236 Right parsable grammar 271—275 398 Right parse see “Rightmost derivation” “Bottom-up Right parse language 273 Right parser 269—271 Right recursive grammar 153 Right sentential form 143 Right-bracketed representation (for trees) 46 Rightmost derivation 142—143 264 327—330 Roberts, P.S. 314 Rogers, H. 36 Rosen, S. 76 Rosenfeld, A. 82 Rosenkrantz, D.J. 102 166 368 Ross, D.T. 263 Rule of inference 19—20 Russell, L.J. 76 Russell’s paradox 2 Salomaa, A. 124 138 211 Samelson, K. 455 Sammet, J.E. 29 58 Sattley, K. 312 Scatter table see “Hash table” Schorre, D.V. 77 313 485 Schutzenberger, M.P. 166 192 211 Schwartz, J.T. 76 Scott, D. 103 124 SDT see “Syntax directed translation” Self-embedding grammar 210 Semantic unambiguity 274 Semantics 55—58 213 Semi-linear set 210 Sentence see “String” Sentence symbol see “Start symbol” Sentential form 86 406—407 414—415 442 Set 1—19 Shamir, E. 211 Shapiro, R.M. 77 Shaw, A.C. 82 Shepherdson, J.C. 124 Shift-reduce parsing 269 301—302 368—371 392 400—403 408 415 418—419 433 438—439 442 “LR(k) “Precedence Simple LL(l) grammar/language 336 Simple mixed-strategy precedence grammar/language 437 448 451—452 Simple precedence grammar/language 403—412 420—424 492—493 507 Simple syntax-directed translation 222—223 230—233 240—242 250 265 512 Single production 149—150 452 Skeletal grammar 440—442 452 Snobol 505—507 Solvable problem see “Problem” Source program 59 Space complexity see “Computational complexity” Spanning tree 51 Standard form (of regular expression equations) 106—110 Standish, T. 77 280 Start state see “Initial state” Start symbol 85 100 168 218 458 State (of a recognizer) 113 168 224 State transition function 113 Stearns, R, E. 192 211 237 368 Steel, T.B. 58 Store function (of a recognizer) 94 Strassen, V. 34 52 String 15 86 Strong characterization see “Characterizing language” Strong connectivity 39 Strong LL(k) grammar 344 348 sub 135 Subset 3 Substitution (of languages) 196—197 Successor 37 Suffix property 17 19 Superset 3 Suppes, P. 3 Symbol table see “Bookkeeping” Symmetric relation 6 Syntactic analysis see “Parsing” Syntax 55—57 Syntax macro 501—503 Syntax tree see “Parse tree” Syntax-directed translation 57 66—70 215—251 445 T-canonical precedence grammar 452—454 T-skeletal grammar 454 Tag system 29 102 Tautology 23 TDPL see “Top-down parsing language” Temporary storage 67—70 Terminal (of a grammar) 85 100 458 Theorem 20 Thompson, K. 138 263 Three address code 65 Time complexity see “Computational complexity” TMG 485 Token 59—63 252 Token set 452 Top-down parsing 178 264—268 285—301 445 456—485 487 Top-down parsing language 458—469 472—473 484—485 Topological sort 43—45 Torii, K. 332 Total function 10 14 Total recursive function 28 Transducer see “Finite transducer” “Pushdown Transformation 71—72 (see also “Function” “Translation”) Transition function see “State transition function” “Next Transition graph 116 225 Transitive closure see “Closure” “Transitive” Transitive relation 6 Translation 55 212—2t3 “Syntax-directed “Transducer”) Translation form (pair of strings) 216—217
Ðåêëàìà
|
|
Î ïðîåêòå