解析技术指南：最新进展与应用实践

需积分: 17 178 浏览量更新于2024-07-18 收藏 2.97MB PDF 举报

《解析技术：实践指南》(第二版)是计算机科学领域的重要参考资料，由David Gries和Fred B. Schneider共同编辑，作为《计算机科学专论》系列的一部分。本书在第一版的基础上，全面更新了格鲁恩和雅各布斯的研究成果，反映了近年来在语法分析，即解析技术领域的最新发展和发现。解析技术，或称句法分析，一直是计算机科学与语言学的核心组成部分。它在两个主要领域发挥着关键作用：一是高级编译器中，普遍采用通用上下文无关文法(CF)解析器来处理程序的语法结构；二是计算语言学，其中这类解析器几乎是不可或缺的工具。解析技术被广泛应用于各种软件产品中，如Web浏览器、计算机设备的解释器和数据压缩程序。在实际应用中，它们有助于正确解析用户输入，确保程序的执行符合预期的语法模式，从而提高软件的可靠性和效率。随着技术的发展，解析技术不断演进，不仅限于基础的词法分析和句法分析，还涉及到更为复杂的功能，如自动机理论、编译器优化、形式语言和自动证明等。例如，书中可能探讨了上下文无关文法的构造、递归下降解析、LL(1)解析器、 Earley解析器或LALR(1)解析器等具体解析算法的设计与实现技巧。此外，该书可能还涵盖了解析器生成器、错误处理策略以及解析性能优化等内容。《计算机科学专论》系列汇集了多学科的知识，展示了在不同主题下的深度探讨，如对象理论、专家系统与概率网络模型、参数化复杂性理论、操作系统多任务处理方法以及软件配置管理等。格鲁恩和雅各布斯的这本书作为其中一本，提供了实用且深入的指导，不仅适合计算机科学专业的学生和研究人员，也是对编程语言、语言学以及相关技术感兴趣的开发者的宝贵参考资源。《Parsing Techniques: A Practical Guide (Monographs in Computer Science)》第二版是一本关于解析技术的综合指南，它紧跟技术进步，深入浅出地介绍了解析理论和实践应用，对于理解和设计高效、精确的语法分析系统具有不可估量的价值。

xviii Contents

5.6 Left-RegularGrammars ..................................... 154

5.7 MinimizingFinite-StateAutomata ............................ 156

5.8 Top-Down Regular Expression Recognition . . .................. 158

5.8.1 The Recognizer . . .................................... 158

5.8.2 Evaluation.......................................... 159

5.9 SemanticsinFSSystems .................................... 160

5.10 FastTextSearchUsingFinite-StateAutomata................... 161

5.11 Conclusion................................................ 162

6 General Directional Top-Down Parsing ..........................165

6.1 ImitatingLeftmostDerivations ............................... 165

6.2 ThePushdownAutomaton................................... 167

6.3 Breadth-FirstTop-DownParsing.............................. 171

6.3.1 AnExample ........................................ 173

6.3.2 A Counterexample: Left Recursion . . . .................. 173

6.4 EliminatingLeftRecursion .................................. 175

6.5 Depth-First(Backtracking)Parsers............................ 176

6.6 RecursiveDescent.......................................... 177

6.6.1 ANaiveApproach ................................... 179

6.6.2 ExhaustiveBacktrackingRecursiveDescent.............. 183

6.6.3 Breadth-FirstRecursiveDescent ....................... 185

6.7 DeﬁniteClauseGrammars................................... 188

6.7.1 Prolog ............................................. 188

6.7.2 TheDCGFormat .................................... 189

6.7.3 Getting Parse Tree Information . . . ...................... 190

6.7.4 Running Deﬁnite Clause Grammar Programs . . ........... 190

6.8 CancellationParsing........................................ 192

6.8.1 CancellationSets .................................... 192

6.8.2 TheTransformationScheme........................... 193

6.8.3 Cancellation Parsing with ε-Rules ...................... 196

6.9 Conclusion................................................ 197

7 General Directional Bottom-Up Parsing .........................199

7.1 ParsingbySearching........................................ 201

7.1.1 Depth-First(Backtracking)Parsing ..................... 201

7.1.2 Breadth-First(On-Line)Parsing........................ 202

7.1.3 ACombinedRepresentation........................... 203

7.1.4 ASlightlyMoreRealisticExample ..................... 204

7.2 TheEarleyParser .......................................... 206

7.2.1 TheBasicEarleyParser............................... 206

7.2.2 The Relation between the Earley and CYK Algorithms. . . . . 212

7.2.3 Handling ε-Rules .................................... 214

7.2.4 Exploiting Look-Ahead . . ............................. 219

7.2.5 LeftandRightRecursion.............................. 224

7.3 ChartParsing.............................................. 226

Contents xix

7.3.1 InferenceRules...................................... 227

7.3.2 ATransitiveClosureAlgorithm ........................ 227

7.3.3 Completion ......................................... 229

7.3.4 Bottom-Up(ActuallyLeft-Corner)...................... 229

7.3.5 TheAgenda......................................... 229

7.3.6 Top-Down.......................................... 231

7.3.7 Conclusion ......................................... 232

7.4 Conclusion................................................ 233

8 Deterministic Top-Down Parsing ...............................235

8.1 Replacing Search by Table Look-Up . . . . ...................... 236

8.2 LL(1)Parsing.............................................. 239

8.2.1 LL(1) Parsing without ε-Rules ......................... 239

8.2.2 LL(1) Parsing with ε-Rules............................ 242

8.2.3 LL(1) versus Strong-LL(1) . . . . . . ...................... 247

8.2.4 FullLL(1)Parsing ................................... 248

8.2.5 Solving LL(1) Conﬂicts . . ............................. 251

8.2.6 LL(1)andRecursiveDescent .......................... 253

8.3 IncreasingthePowerofDeterministicLLParsing ............... 254

8.3.1 LL(k)Grammars..................................... 254

8.3.2 Linear-Approximate LL(k) ............................ 256

8.3.3 LL-Regular ......................................... 257

8.4 Getting a Parse Tree Grammar from LL(1) Parsing. . . . ........... 258

8.5 ExtendedLL(1)Grammars .................................. 259

8.6 Conclusion................................................ 260

9 Deterministic Bottom-Up Parsing ...............................263

9.1 SimpleHandle-FindingTechniques ........................... 265

9.2 Precedence Parsing . ........................................ 266

9.2.1 ParenthesisGenerators................................ 267

9.2.2 Constructing the Operator-Precedence Table . . ........... 269

9.2.3 Precedence Functions. . . . ............................. 271

9.2.4 Further Precedence Methods . . . . . ...................... 272

9.3 Bounded-Right-Context Parsing . ............................. 275

9.3.1 Bounded-Context Techniques . . . . ...................... 276

9.3.2 Floyd Productions . . . . . . ............................. 277

9.4 LR Methods . . . . . . . ........................................ 278

9.5 LR(0) .................................................... 280

9.5.1 TheLR(0)Automaton ................................ 280

9.5.2 UsingtheLR(0)Automaton ........................... 283

9.5.3 LR(0) Conﬂicts . . .................................... 286

9.5.4 ε-LR(0)Parsing ..................................... 287

9.5.5 PracticalLRParseTableConstruction................... 289

9.6 LR(1) .................................................... 290

9.6.1 LR(1) with ε-Rules................................... 295

xx Contents

9.6.2 LR(k > 1)Parsing ................................... 297

9.6.3 Some Properties of LR(k)Parsing ...................... 299

9.7 LALR(1).................................................. 300

9.7.1 ConstructingtheLALR(1)ParsingTables................ 302

9.7.2 Identifying LALR(1) Conﬂicts . . . ...................... 314

9.8 SLR(1) ................................................... 314

9.9 Conﬂict Resolvers . . ........................................ 315

9.10 Further Developments of LR Methods . . . ...................... 316

9.10.1 EliminationofUnitRules ............................. 316

9.10.2 ReducingtheStackActivity ........................... 317

9.10.3 RegularRightPartGrammars.......................... 318

9.10.4 IncrementalParsing .................................. 318

9.10.5 IncrementalParserGeneration ......................... 318

9.10.6 RecursiveAscent .................................... 319

9.10.7 Regular Expressions of LR Languages .................. 319

9.11 Getting a Parse Tree Grammar from LR Parsing . . . . . . ........... 319

9.12 LeftandRightContextsofParsingDecisions ................... 320

9.12.1 TheLeftContextofaState............................ 321

9.12.2 TheRightContextofanItem .......................... 322

9.13 Exploiting the Left and Right Contexts. . . ...................... 323

9.13.1 Discriminating-Reverse(DR)Parsing ................... 324

9.13.2 LR-Regular......................................... 327

9.13.3 LAR(m)Parsing ..................................... 333

9.14 LR(k)asanAmbiguityTest.................................. 338

9.15 Conclusion................................................ 338

10 Non-Canonical Parsers ........................................343

10.1 Top-Down Non-Canonical Parsing . . . . . . ...................... 344

10.1.1 Left-CornerParsing .................................. 344

10.1.2 DeterministicCancellationParsing ..................... 353

10.1.3 Partitioned LL . . . .................................... 354

10.1.4 Discussion.......................................... 357

10.2 Bottom-Up Non-Canonical Parsing. . . . . . ...................... 357

10.2.1 Total Precedence . .................................... 358

10.2.2 NSLR(1) ........................................... 359

10.2.3 LR(k,∞)............................................ 364

10.2.4 Partitioned LR. . . .................................... 372

10.3 General Non-Canonical Parsing . ............................. 377

10.4 Conclusion................................................ 379

11 Generalized Deterministic Parsers ..............................381

11.1 GeneralizedLRParsing ..................................... 382

11.1.1 TheBasicGLRParsingAlgorithm...................... 382

11.1.2 NecessaryOptimizations.............................. 383

11.1.3 Hidden Left Recursion and Loops ...................... 387

Contents xxi

11.1.4 ExtensionsandImprovements ......................... 390

11.2 GeneralizedLLParsing ..................................... 391

11.2.1 SimpleGeneralizedLLParsing ........................ 391

11.2.2 GeneralizedLLParsingwithLeft-Recursion ............. 393

11.2.3 Generalized LL Parsing with ε-Rules.................... 395

11.2.4 GeneralizedCancellationandLCParsing................ 397

11.3 Conclusion................................................ 398

12 Substring Parsing ............................................399

12.1 TheSufﬁxGrammar........................................ 401

12.2 General (Non-Linear) Methods . . ............................. 402

12.2.1 ANon-DirectionalMethod............................ 403

12.2.2 ADirectionalMethod ................................ 407

12.3 Linear-Time Methods for LL and LR Grammars . . . . . . ........... 408

12.3.1 Linear-Time Sufﬁx Parsing for LL(1) Grammars . . . . . . . . . . 409

12.3.2 Linear-Time Sufﬁx Parsing for LR(1) Grammars . . . . . . . . . . 414

12.3.3 Tabular Methods . .................................... 418

12.3.4 Discussion.......................................... 421

12.4 Conclusion................................................ 421

13 Parsing as Intersection ........................................425

13.1 TheIntersectionAlgorithm .................................. 426

13.1.1 The Rule Sets I

rules

, I

rough

,andI ........................ 427

13.1.2 The Languages of I

rules

, I

rough

,andI .................... 429

13.1.3 AnExample:ParsingArithmeticExpressions ............ 430

13.2 TheParsingofFSAs........................................ 431

13.2.1 Unknown Tokens .................................... 431

13.2.2 Substring Parsing by Intersection . ...................... 431

13.2.3 Filtering ............................................ 435

13.3 TimeandSpaceRequirements................................ 436

13.4 Reducing the Intermediate Size: Earley’s Algorithm on FSAs . . . . . . 437

13.5 ErrorHandlingUsingIntersectionParsing...................... 439

13.6 Conclusion................................................ 441

14 Parallel Parsing ..............................................443

14.1 TheReasonsforParallelParsing.............................. 443

14.2 Multiple Serial Parsers . . .................................... 444

14.3 Process-Conﬁguration Parsers . . . ............................. 447

14.3.1 AParallelBottom-upGLRParser ...................... 448

14.3.2 Some Other Process-Conﬁguration Parsers . . . . ........... 452

14.4 ConnectionistParsers ....................................... 453

14.4.1 BooleanCircuits..................................... 453

14.4.2 A CYK Recognizer on a Boolean Circuit . . . . . ........... 454

14.4.3 Rytter’sAlgorithm................................... 460

14.5 Conclusion................................................ 470

xxii Contents

15 Non-Chomsky Grammars and Their Parsers .....................473

15.1 The Unsuitability of Context-Sensitive Grammars . . . . ........... 473

15.1.1 UnderstandingContext-SensitiveGrammars.............. 474

15.1.2 ParsingwithContext-SensitiveGrammars ............... 475

15.1.3 Expressing Semantics in Context-Sensitive Grammars . . . . . 475

15.1.4 ErrorHandlinginContext-SensitiveGrammars........... 475

15.1.5 Alternatives......................................... 476

15.2 Two-LevelGrammars....................................... 476

15.2.1 VWGrammars ...................................... 477

15.2.2 ExpressingSemanticsinaVWGrammar ................ 480

15.2.3 ParsingwithVWGrammars........................... 482

15.2.4 ErrorHandlinginVWGrammars ...................... 484

15.2.5 InﬁniteSymbolSets.................................. 484

15.3 AttributeandAfﬁxGrammars................................ 485

15.3.1 AttributeGrammars.................................. 485

15.3.2 AfﬁxGrammars ..................................... 488

15.4 Tree-AdjoiningGrammars................................... 492

15.4.1 Cross-Dependencies . . . . . ............................. 492

15.4.2 ParsingwithTAGs................................... 497

15.5 Coupled Grammars . ........................................ 500

15.5.1 Parsing with Coupled Grammars . ...................... 501

15.6 OrderedGrammars ......................................... 502

15.6.1 RuleOrderingbyControlGrammar..................... 502

15.6.2 ParsingwithRule-OrderedGrammars................... 503

15.6.3 MarkedOrderedGrammars............................ 504

15.6.4 ParsingwithMarkedOrderedGrammars ................ 505

15.7 Recognition Systems ........................................ 506

15.7.1 Properties of a Recognition System . . . .................. 507

15.7.2 Implementing a Recognition System . . .................. 509

15.7.3 Parsing with Recognition Systems ...................... 512

15.7.4 Expressing Semantics in Recognition Systems . ........... 512

15.7.5 Error Handling in Recognition Systems. . . . . . . ........... 513

15.8 BooleanGrammars......................................... 514

15.8.1 ExpressingContextChecksinBooleanGrammars ........ 514

15.8.2 ParsingwithBooleanGrammars ....................... 516

15.8.3 §-Calculus.......................................... 516

15.9 Conclusion................................................ 517

16 Error Handling ..............................................521

16.1 DetectionversusRecoveryversusCorrection ................... 521

16.2 ParsingTechniquesandErrorDetection........................ 523

16.2.1 Error Detection in Non-Directional Parsing Methods . . . . . . 523

16.2.2 ErrorDetectioninFinite-StateAutomata ................ 524

16.2.3 Error Detection in General Directional Top-Down Parsers . . 524

16.2.4 Error Detection in General Directional Bottom-Up Parsers. . 524

剩余684页未读，继续阅读

Bahir

粉丝: 1
资源: 12

解析技术指南：最新进展与应用实践

Parsing Techniques：A Practical Guide

ParsingTechniques--a practical guide.pdf

Parsing Techniques - A Practical Guide

Parsing techniques_ a practical guide

Parsing Techniques - A Practical Guide.docx

Parsing Techniques - A Practical Guide - 2008

解析技术-实用指南Parsing Techniques - A Practical Guide

Parsing Techniques a Practical Guide

Parsing techiniques A Practical Guide

template parsing error: template: :1: unclosed action

最新资源