# Thuật toán Algorithms (Phần 28)

Chia sẻ: Tran Anh Phuong | Ngày: | Loại File: PDF | Số trang:10

0
40
lượt xem
3

## Thuật toán Algorithms (Phần 28)

Mô tả tài liệu

Tham khảo tài liệu 'thuật toán algorithms (phần 28)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Thuật toán Algorithms (Phần 28)

1. PATTERN MATCHING is the number of the actual initial state. (Note the special representation used for null states with 0 or 1 exits.) Since we often will want to access states just by number, the most suitable organization for the machine is to use the array representation. We’ll use the three arrays ch: amty [O..Mmax] of char; nextl, next2: array [O..Mmax] of integer; Here Mmax is the maximum number of’ states (twice the maximum pattern length). It would be possible to get by with two-thirds this amount of space, since each state really uses only two rreaningful pieces of information, but we’ll forsake this improvement for the sake of clarity and also because pattern descriptions are not likely to be particularly long. We’ve seen how to build up mach.nes from regular expression pattern descriptions and how such machines might be represented as arrays. However, to write a program to do the translation from a regular expression to the corresponding nondeterministic machine representation automatically is quite another matter. In fact, even writing a program to determine if a given regular expression is legal is challenging for the uninitiated. In the next chapter, we’ll study this operation, called parsing, in much more detail. For the moment, we’ll assume that this translation has been done, so that we have available the ch, nextl, and next2 arrays representing a particular nondeterministic machine which corresponds to the regular expression pattern description of interest. Simulating the Machine The last step in the development of a. general regular-expression pattern- matching algorithm is to write a program which somehow simulates the opera- tion of a nondeterministic pattern-matching machine. The idea of writing a program which can “guess” the right answer seems ridiculous. However, in this case it turns out that we can keep track of all possible matches in a systematic way, so that we do eventually encounter the correct one. One possibility would be to develop a recursive program which mimics the nondeterministic machine (but tries all possibilities rather than guessing the right one). Instead of using this approach, we’ll look at a nonrecursive implementation which exposes the basic operating principles of the method by keeping the states under consideration in a rather peculiar data structure called a deque, described in some detail below. The idea is to keep track of all states that could possibly be encountered while the machine is “looking at” the c:lrrent input character. Each of these