Bài giảng Xây dựng chương trình dịch: Bài 3 - Nguyễn Thị Thu Hương

21/1/2010<br /> <br /> Làm thế nào để sản sinh ra các<br /> xâu ?<br /> Văn phạm phi ngữ cảnh có thể dùng để<br /> sản sinh ra các xâu thuộc ngôn ngữ như<br /> sau:<br /> <br /> Bài 3.<br /> Văn phạm sản sinh<br /> <br /> X = Ký hiệu đầu<br /> While còn ký hiệu không kết thúc Y trong X do<br /> Áp dụng một trong các sản xuất của,văn<br /> phạm chẳng hạn Y -> w<br /> <br /> 1<br /> <br /> Ví dụ<br /> <br /> 2<br /> <br /> Suy dẫn (Derivations)<br /> <br /> S -> +A | -A |A<br /> A -> B.B | B<br /> B -> BC | C<br /> C -> 0 | 1 | 2 |. . . .|9<br /> <br /> Mỗi lần thực hiện việc thay thế là một<br /> bước suy dẫn<br /> dẫn.<br /> „ Nếu mỗi dạng câu có nhiều ký hiệu không<br /> kết thúc để thay thế có thể sử dụng bất cứ<br /> sản xuất nào.<br /> „<br /> <br /> Khi X chỉ chứa ký hiệu kết thúc, nó là xâu được<br /> sản sinh bởi văn phạm.<br /> 3<br /> <br /> 4<br /> <br /> 1<br /> <br /> 21/1/2010<br /> <br /> Suy dẫn trái và suy dẫn phải<br /> „<br /> <br /> Cây suy dẫn(Cây phân tích cú pháp)<br /> Cây suy dẫn có những đặc điểm sau<br /> 1) Mỗi nút của cây có nhãn là ký<br /> hiệu kết thúc, ký hiệu không kết<br /> thúc hoặc ε (xâu rỗng)<br /> 2) Nhãn của nút gốc là S (ký hiệu<br /> đầu)<br /> 3) Nút trong có nhãn là ký hiệu<br /> không kết thúc<br /> 4) Nút A có các nút con từ trái qua<br /> phải là X1, X2, ... , Xk thì có một<br /> sản xuất dạng A -> X1 X2 ... Xk<br /> 5)Nút lá có thể có nhãn ε chỉ khi tồn<br /> tại sản xuất A -> ε và nút cha của<br /> nút lá chỉ có một nút con duy nhất<br /> <br /> Nếu giải thuật phân tích cú pháp chọn ký<br /> hiệu không kết thúc cực trái hay cực phải<br /> để thayy thế,, kết q<br /> quả của nó lad suy<br /> y dẫn<br /> trái hoặc suy dẫn phải<br /> <br /> 5<br /> <br /> 6<br /> <br /> Văn phạm nhập nhằng<br /> <br /> Khử nhập nhằng<br /> <br /> Văn phạm<br /> E -> E + E<br /> E -> E * E<br /> E -> ( E )<br /> E -> ident<br /> <br /> E -> E + T<br /> E -> T<br /> T -><br /> >T*F<br /> T -> F<br /> F -> ( E )<br /> F -> ident<br /> <br /> Cho phép đưa ra hai suy dẫn khác nhau cho<br /> xâu ident + ident * ident (chẳng hạn x + y * z)<br /> <br /> (Bằng cách thêm các ký hiệu không kết thúc và các sản xuất để<br /> đảm bảo thứ tự ưu tiên)<br /> <br /> Văn phạm là nhập nhằng<br /> 7<br /> <br /> 8<br /> <br /> 2<br /> <br /> 21/1/2010<br /> <br /> Đệ quy<br /> „<br /> „<br /> <br /> Khử đệ quy trái<br /> <br /> Một sản xuất là đệ qui nếu X =>* ω1X ω2<br /> Có thể dùng để biểu diễn các quá trình lặp hay cấu trúc<br /> lồng nhau<br /> <br /> E -> E + T | T<br /> T -> T * F | F<br /> F -> ( E ) | ident<br /> <br /> Khử đệ<br /> ệq<br /> quy<br /> y trái bằng<br /> g cách thêm ký<br /> ý hiệu<br /> ệ không<br /> g<br /> kết thúc và sản xuất mới<br /> <br /> Đệ quy trực tiếp X =>ω1X ω2<br /> <br /> Đệ quy trái X => b | Xa. X => X a => X a a => X a a a =>b a a a a a ...<br /> Đệ quy phải X => b | a X. X => a X => a a X => a a a X =>... a a a a a b<br /> Đệ quy giữa X => b | "(" X")". X =>(X) =>((X)) =>(((X))) =>(((... (b)...)))<br /> <br /> E -> T E'<br /> E' -> + T E' | ε<br /> T -> F T'<br /> T' -> * F T' | ε<br /> F -> ( E ) | ident<br /> <br /> Đệ quy gián tiếp X =>* ω1X ω2<br /> <br /> 9<br /> <br /> 10<br /> <br /> 3<br /> <br />