Cách nhìn này trực tiếp dẫn tới một phương pháp thật đơn giản để kiểm tra khi nào các biểu thức chính quy là hợp lệ. Một khi tất cả các lệnh gọi thủ tục đã được loại bỏ, ta thấy rằng mỗi ký hiệu kết thúc sẽ chỉ được quét khi nó bị bắt gặp. Việc xử lý duy nhất được thực hiện thực sự là kiểm tra xem có một dấu ngoặc phải sánh được với mỗi một dấu ngoặc trái hay không, khi nào thì mỗidấu "+" là được theo sau bởi một chữ cái hoặc một dấu "(", và khi nào thì mỗi dấu "*" là được theo sau bởi một chữ cái hoặc một dấu ")". Nghĩa là, việc kiểm tra khi nào một biểu thức chính quy là hợp lệ sẽ chủ yếu tương đương với việc kiểm tra xem có sự cân bằng số dấu ngoặc hay không. Điều này có thể được cài đặt một cách đơn giản bằng cách duy trì một biến đếm (counter), được khởi động là 0, được tăng lên khi bắt gặp một dấu ngoặc trái và được giảm đi khi bắt gặp một dấu ngoặc phải. Nếu biến đếm là 0 ở cuối biểu thức, và các ký hiệu "+" và "*" trong biểu thức thoả mãn các yêu cầu vừa được nêu, thì biểu thức là hợp lệ.

Dĩ nhiên, có những phân tích khác hơn là chỉ kiểm tra khi nào dãy nhập vào là hợp lệ: mục đích là để xây dựng cây phân tích (ngay cả theo cách ngầm định, như trong bộ phân tích từ-trên-xuống) cho công việc xử lý khác nữa. Có khuynh hướng là có thể làm điều này với các chương trình với cùng một cấu trúc chủ yếu như bộ kiểm tra dấu ngoặc đã được mô tả trong đoạn trước. Một kiểu bộ phân tích mà nó thực hiện theo cách này thường được gọi là bộ phân tích giảm-phép-dịch-chuyển. Ý tưởng là duy trì một ngăn xếp đẩy xuống (pushdown stack) chứa các ký hiệu kết và chưa kết. Mỗi bước trong việc phân tích sẽ hoặc là một bước dịch-chuyển, trong đó đưon giản là ký tự nhập kế sẽ được cất trên ngăn xếp, hoặc là một bước làm giảm, trong đó các ký tự tại đỉnh ngăn xếp được đối sánh với vế phải của một luật sinh nào đó trong văn phạm và được thay bằng ký tự chưa kết trên vế trái của luật sinh đó. (Khó khăn chính trong việc xây dựng một bộ phân tích giảm-phép-dịch-chuyểnlầ quyết định xem khi nào thì dịch chuyển và khi nào thì làm giảm. Đây có thể là một quyết định phức tạp, phụ thuộc vào văn phạm). Sau này,tất cả các ký tự nhập vào được dịch chuyểnvào trong ngăn xếp, và cuối cùng, ngăn xếp được làm giảm thành một ký hiệu chưa kết đơn lẻ.

Phân tích từ-dưới-lên thường được xem là phương pháp lựa chọn cho các ngôn ngữ lập trình thực sự, và có một tài liệu mở rộng việc phát triển các bộ phân tích cho các bộ văn phạm lớn có kiểu được yêu cầu để mô tả một ngôn ngữ lập trình. Mô tả ngắn gọn của chúng ta chỉ lướt qua bề mặt của các kết quả đã được tạo ra.

Trình biên dịch

Một trình biên dịch có thể được xem như một chương trình dịch một ngôn ngữ thành một ngôn ngữ khác. Ví dụ, một trình biên dịch Pascal dịch các chương trình từ ngôn ngữ Pascal thành ngôn ngữ máy của một máy cụ thể nào đó. Ta sẽ minh hoạ một cách làm điều này bằng cách tiếp tục với ví dụ đối-sánh-mẫu-biểu-thức-chính-quy; tuy nhiên, bây giờ ta mong muốn dịch từ ngôn ngữ của các biểu thức chính quy thành một "ngôn ngữ" cho các máy đối-sánh-mẫu, các mảng ch, next1, next2 của chương trình match (trong chương trình Thuật toán trong Đối sánh mẫu trong kỳ trước).

Tiến trình dịch chủ yếu là "một-một" : Với mỗi ký tự trong mẫu (ngoại trừ các dấu ngoặc đơn), ta muốn sinh ra một trạng thái cho máy đối-sánh-mẫu. Mẹo là lưu giữ dấu vết của thông tin cần thiết để đổ vào trong các mảng next1 và next2. Để làm điều đó ta sẽ chuyển mỗi một thủ tục trong bộ phân tích đệ-quy-xuống thành các hàm mà nó khởi tạo các máy đối-sánh-mẫu. Mỗi hàm sẽ thêm vào các trạng thái mới khi cần vào cuối của các mảng ch, next1 và next2 và trả về chỉ mục của trạng thái khởi đầu của máy đã được khởi tạo (trạng thái cuối sẽ luôn luôn là đầu vào cuối cùng trong các mảng). Ví dụ, hàm được cho dưới đây đối với luật sinh của sẽ tạo ra các trạng thái "hoặc" (or) cho máy đối-sánh-mẫu:

++

fuction expression: integer;

var ti, t2: integer;

begin

t1:=term; expression:=t1;

if p[j]= '+' then

begin

j:= j+1; state:= state+1; t2:=state; expression:=t2; state:=state+1;

setstate(t2, '', expression, t1);

setstate(t2-1,' ', state,state );

end;

end;

++

Hàm này sử dụng một thủ tục setstate mà nó chỉ đơn giản là đặt các đầu vào cho các mảng ch, next1 và next2 được chỉ mục bởi tham số đầu tiên chứa các giá trị được cho trong các tham số thứ 2, thứ 3 và thứ 4 tương ứng. Chỉ mục state lưu giữ tình trạng "hiện hành" của máy đang được xây dựng: Mỗi khi một trạng thái mới được tạo ra, state được tăng lên. Vì vậy các chỉ mục trạng thái cho máy sẽ tương ứng với một dãy lệnh gọi thủ tục cụ thể giữa giá trị của state ở đầu vào và giá trị state ở đầu ra. Chỉ mục trạng thái cuối là giá trị của state lúc thoát ra (chúng ta không thực sự " tạo" các trạng thái cuối cùng bằng cách tăng state trước khi thoát ra, vì điều này khiến cho nó dễ "trộn lẫn" trạng thái cuối cùng với trạng thái khởi đầu sau đó).

Với quy ước này, ta sẽ kiểm chứng (chú ý lệnh gọi đệ quy !) là chương trình ở trên cài đặt quy tắc cho việc tổ hợp hai máy với phép toán or. Trước hết máy dành cho phần đầu của biểu thức được xây dựng (một cách đệ quy), sau đó 2 trạng thái null mới được thêm vào và phần trhứ hai của biểu thức được xây dựng. Trạng thái null đầu tiên (với chỉ mục của biểu thức t2-1) là trạng thái cuối của máy cho phần đầu của biểu thức mà nó được chế tạo thành một trạng thái "no-op" để nhảy tới trạng thái kết thúc của máy cho phần thứ hai của biểu thức như được yêu cầu. Trạng thái null thứ hai (với chỉ mục t2) là trạng thái khởi đầu, như thế chỉ mục của nó là giá trị trả về cho expression và các đầu vào next1 và next2 được tạo ra để chỉ tới những trạng thái khởi đầucủa hai biểu thức. Chú ý là những biểu thức này được cấu tạo theo thứ tự đảo ngược với những gì ta mong muốn, do giá trị của state cho trạng thái no-op là không biết được cho đến khi lệnh gọi đệ quy tới expression được tạo ra.

Hàm trước tiên xây dựng một cái máy cho một và sau đó, nếu cần, trộn trạng thái kết thúc của máy đó với trạng thái khởi đầu của máy cho một khác. Điều này dễ dàng được thực hiện vì state là chỉ mục trạng thái kết thúc của lệnh gọi tới factor. Một lệnh gọi tới term mà không tăng state được thực hiện mẹo sau:

++

function term;

var t: integer;

begin

term:=factor;

if (p[j] = '(' ) or letter(p[j]) then

t:=term

end;

++

(chúng ta không cần dùng đến chỉ mục trạng thái khởi đầu được trả về bởi lệnh gọi thứ hai tới term, nhưng Pascal yêu cầu chúng ta đặt nó vào đâu đó, do đó ta sẽ bỏ nó vào một biến tạm i)

Hàm cho sử dụng các kỹ thuật tương tự để kiểm soát ba trường hợp của nó: một dấu ngoặc đại diện cho một lệnh gọi đệ quy trên expression; một ký hiệu v đại diện cho phép nối một trạng thái mới cuối chuỗi; và một dấu * đại diện cho các phép toán tương tự như các phép toán trong expression.

++

funtion factor;

var t1, t2: integer;

begin t1:=state;

if p[j] = '(' then

begin

j:= j+1; t2:= expression;

if p[j]=')' then j:=j+1 else error

end

else if letter(p[j]) then

begin

setstate(state, p[j], state+1, state+1);

t2:= state; j:=j+1; state:=state+1

end;

else error;

if p[j] <> '*' then factor:= t2 else

begin

setstate(state,' ', state+1, t2);

factor:=state; next1[t1-1]:= state;

j:= j+1; state:= state+1;

end;

end;

++

Với ví dụ của chúng ta, làm thế nào các trạng thái được kiến tạo cho mẫu (A*B+AC)D. Đầu tiên, trạng thái 1 được xây dựng cho A. Sau đó, trạng thái 2 được xây dựng cho toán hạng kết (closure) và trạng thái 3 được gắn vào cho B. Kế đó, dấu "+" được bắt gặp và các trạng thái 4, 5 được xây dựng bởi expression, nhưng các vùng của chúng không thể được đổ đầy cho đến khi thực hiện xong một lệnh gọi đệ quy với expression, và điều này cuối cùng gây ra việc tạo dựng các trạng thái 6 và 7. Cuối cùng phéo nối của D được điều khiển bởi trạng thái 8, để lại trạng thái 9 như là trạng thái kết thúc.

Bước cuối cùng trong việc phát triển một thuật toán đối-sánh-mẫu biểu-thức-chính-quy là gắn các thủ tục này lại với nhau cùng thủ tục match:

++

procedure matchall;

begin

j:=1; state:=1; next[0]:= expression;

setstate(state, ' ', 0,0);

for i:=1 to N-1 do

if match(i) >= i then

writeln(i);

end;

++

Chương trình này in ra tất cả các vị trí ký tự trong một chuỗi văn bản a[1..N] ở đó có một mẫu p[1..M] dẫn tới sự trùng khớp.

School@net