RagelUserGuide_ragel资源-CSDN文库

Ragel

需积分: 9 71 浏览量 2014-02-12 22:15:09 上传评论收藏 579KB PDF 举报

资源详情

资源评论

Ragel State Machine Compiler

User Guide

Adrian Thurston

Contents

1 Introduction 1

1.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.5 Development Status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Constructing State Machines 6

2.1 Ragel State Machine Speciﬁcations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.1.1 Naming Ragel Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.2 Machine Deﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.3 Machine Instantiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.4 Including Ragel Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.1.5 Importing Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Lexical Analysis of a Ragel Block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 Basic Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4 Operator Precedence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.5 Regular Language Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.5.1 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5.2 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5.3 Diﬀerence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5.4 Strong Diﬀerence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5.5 Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.5.6 Kleene Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.7 One Or More Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5.8 Optional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5.9 Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5.10 Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.5.11 Character-Level Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.6 State Machine Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.7 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 User Actions 19

3.1 Embedding Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.1 Entering Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.2 Finishing Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.1.3 All Transition Action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

CONTENTS iii

3.1.4 Leaving Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2 State Action Embedding Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.1 To-State and From-State Actions . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.2.2 EOF Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2.3 Handling Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.3 Action Ordering and Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 Values and Statements Available in Code Blocks . . . . . . . . . . . . . . . . . . . . 25

4 Controlling Nondeterminism 28

4.1 Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.2 Guarded Operators that Encapsulate Priorities . . . . . . . . . . . . . . . . . . . . . 31

4.2.1 Entry-Guarded Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2.2 Finish-Guarded Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.2.3 Left-Guarded Concatenation . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2.4 Longest-Match Kleene Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

5 Interface to Host Program 35

5.1 Variables Used by Ragel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.2 Alphtype Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.3 Getkey Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.4 Access Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.5 Variable Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5.6 Pre-Push Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.7 Post-Pop Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.8 Write Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.8.1 Write Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.8.2 Write Start, First Final and Error . . . . . . . . . . . . . . . . . . . . . . . . 39

5.8.3 Write Init . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.8.4 Write Exec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.8.5 Write Exports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.9 Maintaining Pointers to Input Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.10 Specifying the Host Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.11 Choosing a Generated Code Style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

6 Beyond the Basic Model 44

6.1 Parser Modularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

6.2 Referencing Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.3 Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6.4 State Charts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.4.1 Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.2 Label . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.3 Epsilon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.4 Simplifying State Charts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.5 Dropping Down One Level of Abstraction . . . . . . . . . . . . . . . . . . . . 50

6.5 Semantic Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.6 Implementing Lookahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6.7 Parsing Recursive Language Structures . . . . . . . . . . . . . . . . . . . . . . . . . . 52

Chapter 1

Introduction

1.1 Abstract

Regular expressions are used heavily in practice for the purpose of specifying parsers. They are

normally used as black boxes linked together with program logic. User actions are executed in

between invocations of the regular expression engine. Adding actions before a pattern terminates

requires patterns to be broken and pasted back together with program logic. The more user actions

are needed, the less the advantages of regular expressions are seen.

Ragel is a software development tool that allows user actions to be embedded into the transi-

tions of a regular expression’s corresponding state machine, eliminating the need to switch from

the regular expression engine and user code execution environment and back again. As a result,

expressions can be maximally continuous. One is free to specify an entire parser using a single reg-

ular expression. The single-expression model aﬀords concise and elegant descriptions of languages

and the generation of very simple, fast and robust code. Ragel compiles executable ﬁnite state

machines from a high level regular language notation. Ragel targets C, C++, Objective-C, D, Java

and Ruby.

In addition to building state machines from regular expressions, Ragel allows the programmer

to directly specify state machines with state charts. These two notations may be freely combined.

There are also facilities for controlling nondeterminism in the resulting machines and building

scanners using patterns that themselves have embedded actions. Ragel can produce code that is

small and runs very fast. Ragel can handle integer-sized alphabets and can compile very large state

machines.

1.2 Motivation

When a programmer is faced with the task of producing a parser for a context-free language

there are many tools to choose from. It is quite common to generate useful and eﬃcient parsers

for programming languages from a formal grammar. It is also quite common for programmers

to avoid such tools when making parsers for simple computer languages, such as ﬁle formats and

communication protocols. Such languages are often regular and tools for processing the context-free

languages are viewed as too heavyweight for the purpose of parsing regular languages. The extra

run-time eﬀort required for supporting the recursive nature of context-free languages is wasted.

When we turn to the regular expression-based parsing tools, such as Lex, Re2C, and scripting

languages such as Sed, Awk and Perl we ﬁnd that they are split into two levels: a regular expression

matching engine and some kind of program logic for linking patterns together. For example, a Lex

剩余55页未读，继续阅读

评论收藏

内容反馈

Ragel User Guide

评论0

最新资源

Ragel User Guide

评论0

最新资源

相关推荐

ragel-guide-6.10.pdf

ragel 状态机

User Guide

LMK04832EVM User’s Guide

ArchiMate User Guide

James User Guide

Ragel有限状态机编译器 - win32bin

ragel测试程序.zip

ragel-6.10.tar.gz

Ragel 6.7 windows版本

BrightSign User Guide

CDRouter User’s Guide

Control-M_User_Guide

TrueCrypt 7 User Guide

PCIE User Guide

Ragel 6.9 windows版本

ragel-windows:适用于 Windows 的 Ragel

ragel-machinery：vil与Ragel和Go一起自动执行魔鬼动作，使您更加快乐

ragel:bíogoragel实用程序存储库

ragel-samples:凝胶样品

DotNetNuke 5 User’s Guide

IMM User Guide

VCS User Guide

AT Command User Guide

Cygwin User's Guide

gherkin2, 在 Ragel ( Cucumber 后面的解析器) 中，快速Gherkin解析器.zip

RagelMSBuildTask：nuget的Ragel msbuild任务

ragel-cheat-sheet:Ragel 状态机编译器备忘单。 (GPLv2+)