有沒有用「真實」語言抽取引理的例子？

L = {0 ^ÑÑÑ：N ≥ 0}

（順便說一下，是不一個上下文無關的語言）。

但我感興趣的是：是否有任何使用任何遠程真實或有用語言的例子？我一直無法找到任何。這些東西之一還是純粹的理論價值，絕對沒有實際應用？

2010-01-26 cletus

能夠證明一種語言是否經常使用？ – 2010-01-26 01:37:16

@Anon：是的，因爲語言是否可以用上下文無關語法來描述對解析器生成器是有價值的。 – cletus 2010-01-26 01:38:42

我花了一段時間才弄清楚爲什麼L不是上下文無關的語言。我認爲一個很好的方法來思考答案是：如果你想寫n 0的話，通過向堆棧添加一些東西來追蹤它。然後打印n 1，通過刪除堆棧中的所有項目來跟蹤。但是，現在沒有辦法記住n是打印n 2的。 – 2010-03-13 17:31:24

L = {0 ^ÑÑ：N ≥ 0}是一個上下文無關語言。

在表達括號匹配可以被認爲是類似的形式的即

L = {（^Ñ）^Ñ：N ≥ 0}

2010-01-26 01:39:57 Arnkrishn

呃......這些都不是我稱之爲「真實」的語言。我知道它是如何應用於這些人造的例子。我想要的是至少有一個它被應用於編程語言或任何遠程「現實世界」的例子。 – cletus 2010-01-26 02:17:19

匹配圓括號（或括號，引號）是不是現實世界？ – 2010-07-16 13:54:17

實際用途之一是，每個人可以停止嘗試構建有限自動機來識別C＃或Fortran的語法。

另一個實際用途是，每個人都可以停止嘗試構建一個下推自動機來識別C＃或Fortran的語義。（即使在Fortran中，如果拼錯了變量名稱，您將獲得一個免費的新變量，但新變量可能不適用於您打算命名其中一個聲明變量時編碼的操作員。）

2010-01-26 01:59:06

我並沒有描述爲什麼它很有用，但它如何被應用到真正的語言，而不是abc或012的序列。 – cletus 2010-01-26 02:16:11

@cletus設計編譯器是在真實世界之外，以非真實語言進行設計的嗎？ – 2010-01-26 21:30:15

「Is這些東西還是純粹的理論價值，絕對沒有實際應用？「

Hrm。什麼是實際應用？你明智地標記了你的問題「計算機科學」。所以，我想你的問題意味着要問，「是不是實用的計算機科學？

在這種情況下，答案是...

當然是！這是教作爲第一途徑之一對於不同的語言複雜性類進行分類，不僅僅是「big-O（whateverthehell）」它表明除了運行時之外，還有一些關於計算的問題，在這種情況下，某些模型根本無法計算某些函數* 這是一個相當低的 - 關於自動機理論的正式證明的球介紹

大部分計算機科學專業的學生（我的同學）熱衷於避免的是計算理論，這是一種抽象外觀明顯落後的分類。

這個充滿希望的事實是計算理論是否是計算機科學的基礎。爲了不掌握不同複雜類別的想法（大O本身並不能削減它）不會拼寫出計算機科學家的死亡，但它將隱藏他或她的視野中相當大一部分的領域。

*是的，通常暫停問題顯示爲第一次，但他們從來沒有第一次得到它。

至於你的問題可能是對你的問題更加憤世嫉俗的解釋，你的意思是「任何一個軟件真的使用這個？」，我的答案當然不是。它是計算基礎的一部分，而不是其應用。這不是對其申請表示不屑一顧，完全沒有。兩者都是平等的，高貴的價值。

2010-01-26 21:20:27 agorenst

這是一個可愛的演講和所有，但它並沒有回答這個問題：我在使用它的真實世界的例子 – cletus 2010-01-26 21:52:58

也許你錯過了森林的樹木**教育**或者你最好澄清你認爲「真實世界」是什麼意思？ – agorenst 2010-01-27 06:23:04

這Python程序是有效的：

print ((((((((((((((((((((((((1))))))))))))))))))))))))

以及與右側等量的(在左側和)所有其它等效的語句。

您不能構建正則表達式來驗證，因此您必須使用解析器。

這完全不是理論上的。這是你不能使用正則表達式來解析HTML的原因。

2010-07-16 06:26:57

回答