Regular vs Context Free Grammars

Question

Tôi đang học cho các ngôn ngữ tính toán của mình và có một ý tưởng tôi đang gặp phải vấn đề trong đầu.

Tôi hiểu rằng ngữ pháp thông thường đơn giản hơn và không thể chứa sự mơ hồ, nhưng không thể thực hiện nhiều công việc cần thiết cho ngôn ngữ lập trình. Tôi cũng hiểu rằng ngữ cảnh không có ngữ cảnh cho phép sự mơ hồ, nhưng cho phép một số thứ cần thiết cho ngôn ngữ lập trình (như palindromes).

Điều tôi đang gặp phải là tìm hiểu cách tôi có thể lấy được tất cả những điều trên bằng cách biết rằng các phân tích ngữ pháp thông thường có thể ánh xạ tới một thiết bị đầu cuối hoặc nonterminal theo sau bởi một thiết bị đầu cuối hoặc bản đồ nonterminal không có ngữ cảnh bất kỳ sự kết hợp của thiết bị đầu cuối và nonterminals.

Ai đó có thể giúp tôi kết hợp tất cả điều này với nhau không?

Answer 1

Ngữ pháp thông thường là đúng hoặc trái tuyến tính, trong khi ngữ cảnh ngữ pháp tự do về cơ bản là bất kỳ sự kết hợp nào của thiết bị đầu cuối và không phải thiết bị đầu cuối. Do đó bạn có thể thấy rằng ngữ pháp thông thường là một tập con ngữ pháp không có ngữ cảnh.

Vì vậy, đối với một palindrome ví dụ, có dạng,

S->ABA 
A->something 
B->something 

Bạn có thể thấy rõ rằng palindromes không thể được thể hiện bằng ngữ pháp thường xuyên kể từ khi nó cần phải được một trong hai phải hoặc trái tuyến tính và như vậy không thể có một thiết bị không ở cả hai bên.

Vì ngữ pháp thông thường không mơ hồ, nên chỉ có một quy tắc sản xuất cho một thiết bị không phải là thiết bị đầu cuối, trong khi có thể có nhiều hơn một ngữ pháp trong trường hợp ngữ pháp không có ngữ cảnh.

Answer 2

Tôi nghĩ rằng những gì bạn muốn suy nghĩ về các loại bơm máu khác nhau. Một ngôn ngữ thông thường có thể được công nhận bởi một automaton hữu hạn. Một ngôn ngữ không có ngữ cảnh yêu cầu một chồng và ngôn ngữ nhạy cảm theo ngữ cảnh yêu cầu hai ngăn xếp (tương đương với việc nói nó đòi hỏi một máy Turing đầy đủ.)

Vì vậy, nếu chúng ta nghĩ về pumping lemma for regular languages, về cơ bản, được rằng bất kỳ ngôn ngữ thông thường có thể được chia thành ba mảnh, x, y, và z, nơi mà tất cả các trường hợp của ngôn ngữ trong xy * z (nơi * là Kleene lặp lại, tức là 0 hoặc nhiều bản sao của y.) Về cơ bản bạn có một "nonterminal" có thể được mở rộng.

Bây giờ, về ngôn ngữ không có ngữ cảnh thì sao? Có một tương tự pumping lemma for context-free languages mà phá vỡ các chuỗi trong ngôn ngữ thành năm phần, uvxyz, và nơi mà tất cả các trường hợp của ngôn ngữ trong uv ⁱ xy ⁱ z, cho tôi ≥ 0. Bây giờ, bạn có hai "nonterminals" có thể được sao chép hoặc được bơm, miễn là bạn có cùng số.

Answer 3

một ngữ pháp thông thường không bao giờ mơ hồ vì nó là tuyến tính tuyến tính hoặc trái nên chúng tôi không thể tạo hai cây quyết định cho ngữ pháp thông thường để nó luôn rõ ràng.nhưng khác với ngữ pháp thông thường tất cả đều có thể hoặc có thể không thường xuyên

Answer 4

Ngữ pháp không có ngữ cảnh nếu tất cả các quy tắc sản xuất có dạng: A (nghĩa là, bên trái của quy tắc chỉ có thể là một biến duy nhất; bên phải là không hạn chế và có thể là bất kỳ chuỗi các thiết bị đầu cuối và các biến). Chúng ta có thể định nghĩa ngữ pháp là 4-tuple trong đó V là một tập hữu hạn (các biến), _ là một tập hợp hữu hạn (terminal), S là biến bắt đầu, và R là một tập hợp các quy tắc hữu hạn, lập bản đồ V
ngữ pháp thông thường hoặc là phải hoặc trái tuyến tính, trong khi ngữ cảnh ngữ pháp tự do về cơ bản là bất kỳ sự kết hợp nào giữa các thiết bị đầu cuối và không phải thiết bị đầu cuối. do đó chúng ta có thể nói rằng ngữ pháp thông thường là một tập con ngữ pháp không có ngữ cảnh. Sau khi các đặc tính này chúng ta có thể nói rằng Context miễn phí Ngôn ngữ thiết cũng chứa Ngôn ngữ thường xuyên thiết lập

Answer 5

Regular Expressions

• Cơ sở phân tích từ vựng
• Đại diện cho ngôn ngữ thường xuyên

Context miễn ngữ pháp

• Cơ sở phân tích cú pháp
• Đại diện cho ngôn ngữ xây dựng

Answer 6

Về cơ bản thường xuyên ngữ pháp là một tập hợp con của bối cảnh tự do ngữ pháp, nhưng chúng tôi không thể nói Mỗi bối cảnh tự do ngữ pháp là một ngữ pháp thông thường. Chủ yếu ngữ cảnh ngữ pháp tự do là mơ hồ và ngữ pháp thông thường có thể không rõ ràng.

Answer 7

ngữ pháp thông thường: - ngữ pháp có chứa sản xuất như sau là RG:

V->TV or VT 
V->T 

đó V = biến và T = terminal

RG chưa trái tuyến tính Grammar hoặc phải Liner Grammar, nhưng không Ngữ pháp tuyến tính ở giữa.

Như chúng ta đã biết, tất cả RG đều là Ngữ pháp tuyến tính nhưng chỉ có Ngữ pháp tuyến tính hoặc tuyến tính bên phải là RG.

Ngữ pháp thông thường có thể không rõ ràng.

S->aA|aB 
A->a 
B->a 

nhập nhằng Grammar: - cho một chuỗi x tồn tại của họ nhiều hơn một LMD hoặc Hơn RMD hoặc Hơn một cây Parse hoặc Một LMD và One RMD nhưng cả hai Sản xuất cây Parse khác nhau.

   S     S 

      / \    / \ 
      a  A    a  B 
        \     \ 
        a     a 

Ngữ pháp này không rõ ràng Ngữ pháp vì hai cây phân tích.

CFG: - Một ngữ pháp cho là CFG nếu sản xuất của nó là ở dạng:

V->@ where @ belongs to (V+T)* 

DCFL: - như chúng ta biết tất cả DCFL là LL (1) Ngữ pháp và tất cả LL (1) là LR (1) vì vậy nó không bao giờ mơ hồ. vì vậy DCFG không bao giờ mơ hồ.

Chúng tôi cũng biết tất cả RL là DCFL nên RL không bao giờ mơ hồ. Lưu ý rằng RG có thể không rõ ràng nhưng RL thì không.

CFL: CFl Có thể hoặc không rõ ràng.

Lưu ý: RL không bao giờ có thể mơ hồ.

Answer 8

Sự khác biệt giữa bình thường và bối cảnh tự do ngữ pháp: (N, Σ, P, S): thiết bị đầu cuối, không thuộc đầu cuối, tác phẩm, bắt đầu từ trạng thái ga hiệu

● những biểu tượng cơ bản của ngôn ngữ xác định bởi một chính thức ngữ pháp

● abc

những biểu tượng không thuộc đầu cuối (hoặc các biến cú pháp)

● thay thế bởi nhóm thiết bị đầu cuối những biểu tượng theo các quy tắc sản xuất

● ABC

thường xuyên ngữ pháp: phải hoặc trái đều đặn ngữ pháp đúng thường xuyên ngữ pháp, tất cả các quy tắc tuân theo hình thức

1. B → một trong đó B là một không thuộc đầu cuối trong N và a là một đầu cuối trong Σ
2. B → aC trong đó B và C ở N và a nằm trong Σ
3. B → ε trong đó B bằng N và ε biểu thị đường rỗng g, tức là chuỗi có độ dài 0

trái thường xuyên ngữ pháp, tất cả các quy tắc tuân theo hình thức

1. A → một trong đó A là một không thuộc đầu cuối trong N và a là một thiết bị đầu cuối trong Σ
2. A → Ba trong đó A và B là trong N và một là ở Σ
3. A → ε trong đó A là N và ε là chuỗi rỗng

bối cảnh tự do ngữ pháp (CFG)

○ ngữ pháp chính thức, trong đó mọi quy tắc sản xuất có dạng V → w

○ V là một biểu tượng không thuộc đầu cuối đơn

○ w là một chuỗi các thiết bị đầu cuối và/hoặc nonterminals (w có thể trống)