이것은 문법 프로그램입니까? 의 재구성입니다 . Vag가 이전에 요청했으며 주석 작성자의 많은 제안이 있습니다.

문법은 어떤 방식으로 계산 모델을 지정하는 것으로 볼 수 있습니까? 예를 들어 다음과 같은 간단한 문맥없는 문법을 사용하는 경우

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

파서가 여기에서 설명한 것처럼 터미널 과 비 터미널 기호를 구분하지 않는다고 가정하면 최대 3의 숫자에 대해 간단한 산술을 수행 할 수 있습니다.

예를 들어, 문자열을

"2 + 0 + 1"

이 문자열에서 LR (1) 파서를 실행 하면 계산 결과가 트리의 루트에 저장되는 다음과 같은 구체적인 구문 트리 가 제공됩니다.

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0'

따라서 문법을 프로그램 으로, 파서 생성기를 컴파일러로 사용 하면 문법 사양 언어를 프로그래밍 언어로 볼 수 있습니까?

또한 celullar automata 또는 lambda calculus를 사용 하여 튜링 완료 프로그램을 빌드하는 방법과 유사한 문법을 ​​지정하여 튜링 완료 프로그램을 작성할 수 있습니까?

바꾸어 말하면, 언어 를 인식 한다는 의미에서 , 정규 언어 는 유한 상태 오토마타에 대응하고 , 문맥이없는 언어는 오토마타 를 푸시 다운 하고, 문맥에 민감한 언어 는 선형 경계 오토마타에 대응하는 것으로 알려져있다 . 그러나 문법을 계산 장치 ( 위의 예에서 의미하는 프로그램 )로 보는 경우 Chomsky 계층 구조에서 각 문법 클래스의 계산 강도 를 어떻게 분류 합니까?

• 정규 문법
• 문맥없는 문법
• 상황에 맞는 문법
• 무제한 문법 ( 재귀 열거 형 언어의 경우 )

또한 문법의 하위 클래스 (예 :

• 결정 론적 맥락이없는 문법 ( LR (k) / LL (k) / SLR / LALR 등)
• 중첩 된 단어 문법
• 트리 인접 문법
• 색인화 된 문법

편집 : 그건 그렇고, 이것은 내 자신의 질문에 대한 이쑤시개이지만 나는 예제 문법에 대한 시작 상징을주지 않았고 터미널과 비 터미널을 구별 할 필요성에 수동으로 흔들렸다는 언급은하지 않았다. 기술적으로 또는 전통적으로 나는 문법이 아마도 다음과 같은 좀 더 복잡한 형태로 작성되어야한다고 생각합니다 (여기서 S는 시작 기호이고 $ 는 스트림 끝 터미널을 나타냄).

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

… 아무것도 바뀌지 않지만 언급해야한다고 생각했습니다.

편집 : gasche의 대답을 읽을 때 염두에 두었던 것은 내 예제에서 트리의 각 분기가 하위 계산을 나타냅니다. 각 생산 규칙을 ​​LHS가 결과를 나타내고 RHS가 인수를 나타내는 함수로 보는 경우 문법 구조에 따라 함수 구성 방법이 결정됩니다.

다시 말해, 파서의 lookahead 메커니즘과 함께 어떤 함수를 적용 할 것인지 (parametric polymorphism과 같은 ‘kinda’)뿐만 아니라 새로운 함수를 형성하기 위해 어떻게 구성해야하는지 결정하는 데 도움이됩니다.

적어도, 나는 당신이 그것을 모호하지 않은 CFG에 대해 이런 식으로 볼 수 있다고 생각합니다. 다른 문법에 대해서는 정신 체조가 지금 나에게 조금 너무 많습니다.

답변

S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

0   // zero
#0  // one
##0 // two

S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

#####0 + ####0

1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X