컨텍스트가없는 프로그래밍 언어는 무엇입니까?

컨텍스트가없는 프로그래밍 언어는 무엇입니까?

---

또는 좀 더 정확하게 말하면 문맥없는 문법으로 정의되는 프로그래밍 언어는 무엇입니까?

내가 수집 한 것에서 C ++는 매크로 및 템플릿과 같은 것들로 인해 컨텍스트 프리가 아닙니다. 내 직감에 따르면 기능적 언어는 컨텍스트가 없을 수 있지만이를 백업 할 하드 데이터가 없습니다.

간결한 예에 대한 추가 담당자 :-)

---

구문 상 올바른 프로그램 세트는 거의 모든 언어에 대해 컨텍스트가 없습니다.

컴파일되는 프로그램 세트는 거의 모든 언어에 대해 컨텍스트 프리가 아닙니다. 예를 들어 모든 컴파일 C 프로그램 집합이 컨텍스트가없는 경우 정규 언어 (정규식이라고도 함)와 교차하여 일치하는 모든 컴파일 C 프로그램 집합

^int main\(void\) { int a+; a+ = a+; return 0; }$

문맥 자유롭지 만 문맥 자유롭지 않은 것으로 잘 알려진 언어 a ^ kba ^ kba ^ k와 분명히 동형 입니다.

---

컨텍스트가없는 프로그래밍 언어는 무엇입니까? [...]

내 직감은 기능적 언어가 문맥 자유로울 수 있다고 알려준다 ...]

짧은 버전 : 단어의 어떤 의미에서도 문맥이없는 실제 프로그래밍 언어는 거의 없습니다. 언어가 문맥에 영향을받지 않는지 여부는 기능과 관련이 없습니다. 단순히 언어 규칙과 기능이 구문 분석하는 데 얼마나 복잡한 지 문제입니다.

다음은 명령형 언어 Brainfuck에 대한 CFG입니다 .

Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'

다음은 기능적 SKI 결합기 미적분에 대한 CFG입니다 .

Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'

이 CFG 는 매우 간단하기 때문에 두 언어의 모든 유효한 프로그램을 인식 합니다 .

---

더 긴 버전 : 일반적으로 CFG (context-free grammars)는 언어의 구문 을 대략적으로 지정하는 데만 사용 됩니다. 문법적으로 올바른 프로그램 과 컴파일하는 프로그램을 구별해야합니다 . 가장 일반적으로, 컴파일러 언어로 분석 분할 구문 분석 코드 조각의 일반적인 구조를 구축하고 확인하고, 의미 분석을 했는지 확인하는 의미 프로그램.

"문맥없는 언어"가 " ... 모든 프로그램이 컴파일되는 "을 의미 한다면, 대답은 거의 없습니다. 이 법안에 맞는 언어에는 변수의 존재, 공백 민감도, 유형 시스템 또는 기타 컨텍스트 와 같은 규칙이나 복잡한 기능이 거의 없습니다 . 정보는 한 곳에서 정의되고 다른 곳에서는 의존합니다.

반면에 "문맥없는 언어"가 " 모든 프로그램이 구문 분석을 통과하는 ... "을 의미 하는 경우 , 그 대답은 구문 자체가 얼마나 복잡한가에 달려 있습니다. CFG만으로는 설명하기 어렵거나 불가능한 많은 구문 기능이 있습니다. 이들 중 일부는 카운터, 조회 테이블 등을 추적하기 위해 파서에 상태를 추가하여 극복합니다.

CFG로 표현할 수없는 구문 기능의 예 :

• Python 및 Haskell과 같은 들여 쓰기 및 공백에 민감한 언어. 임의로 중첩 된 들여 쓰기 수준을 추적하는 것은 본질적으로 상황에 따라 달라지며 들여 쓰기 수준에 대해 별도의 카운터가 필요합니다. 각 레벨에 사용되는 공간 수와 레벨 수 모두.

  고정 된 양의 공백을 사용하여 고정 된 수준의 들여 쓰기 만 허용하는 것은 각 수준의 들여 쓰기에 대해 문법을 복제하는 방식으로 작동하지만 실제로는 불편합니다.

• C으로 typedef 구문 분석 문제는 뭔가 일반 식별자 또는 기존 유형에 대한 형식 정의 별칭 인 경우 혼자 문법에서 알 수 없기 때문에 C 프로그램은 어휘 분석 중 모호한 것을 말한다.

  예는 다음과 같습니다.

    typedef int my_int;
    my_int x;
  

  세미콜론에서 유형 환경은 my_int에 대한 항목으로 업데이트되어야합니다. 그러나 렉서가 이미 my_int를 봤다면 타입 이름이 아닌 식별자로 렉싱했을 것입니다.

• Lisp, C ++, Template Haskell, Nim 등과 같은 매크로 및 템플릿 기반 언어. 구문이 분석되는 동안 구문이 변경되므로 한 가지 해결책은 구문 분석기를 자체 수정 프로그램으로 만드는 것입니다. " C ++는 문맥에 영향을받지 않습니까? 아니면 문맥에 민감합니까? "를 참조하십시오.

• 종종 연산자 우선 순위와 연관성 은 가능 하더라도 CFG에서 직접 표현되지 않습니다 . 예를 들어 ^가 ×보다 더 빡빡하고 ×가 +보다 더 빡빡한 작은 표현식 문법에 대한 CFG는 다음과 같을 수 있습니다.

  E → E ^ E
  E → E × E
  E → E + E
  E → (E)
  E → num
  

  그러나이 CFG는 모호 하며 종종 ^가 가장 빡빡하게 결합하고 ×가 +보다 더 단단하게 결합하고 ^가 오른쪽 결합이며 ×와 +가 왼쪽 결합임을 나타내는 우선 순위 / 결합 테이블이 수반됩니다 .

  우선 순위 및 연관성은 기계적인 방식으로 CFG로 인코딩 될 수 있으므로 명확하고 연산자가 올바르게 작동하는 구문 트리 만 생성합니다. 위의 문법에 대한 예 :

  E₀ → EA E₁
  EA → E₁ + EA
  EA → ε
  E₁ → EM E₂
  EM → E₂ × EM
  EM → ε
  E₂ → E₃ EP
  EP → ^ E₃ EP
  E₃ → num
  E₃ → (E₀)
  

  그러나 모호한 CFG + 우선 순위 / 연관성 테이블은 더 읽기 쉽고 다양한 유형의 LR 파서 생성기 라이브러리가 더 큰 크기의 명확하고 변형 된 문법을 처리하는 대신 이동 / 감소 충돌 을 제거 하여 더 효율적인 파서를 생성 할 수 있기 때문에 일반적 입니다.

In theory, all finite sets of strings are regular languages, and so all legal programs of bounded size are regular. Since regular languages are a subset of context-free languages, all programs of bounded size are context-free. The argument continues,

While it can be argued that it would be an acceptable limitation for a language to allow only programs of less than a million lines, it is not practical to describe a programming language as a regular language: The description would be far too large.
     — Torben Morgensen's Basics of Compiler Design, ch. 2.10.2

The same goes for CFGs. To address your sub-question a little differently,

Which programming languages are defined by a context-free grammar?

Most real-world programming languages are defined by their implementations, and most parsers for real-world programming languages are either hand-written or uses a parser generator that extends context-free parsing. It is unfortunately not that common to find an exact CFG for your favourite language. When you do, it's usually in Backus-Naur form (BNF), or a parser specification that most likely isn't purely context-free.

Examples of grammar specifications from the wild:

• BNF for Standard ML
• BNF-like for Haskell
• BNF for SQL
• Yacc grammar for PHP

---

Depending on how you understand the question, the answer changes. But IMNSHO, the proper answer is that all modern programming languages are in fact context sensitive. For example there is no context free grammar that accepts only syntactically correct C programs. People who point to yacc/bison context free grammars for C are missing the point.

---

To go for the most dramatic example of a non-context-free grammar, Perl's grammar is, as I understand it, turing-complete.

---

If I understand your question, you are looking for programming languages which can be described by context free grammars (cfg) so that the cfg generates all valid programs and only valid programs.

I believe that most (if not all) modern programming languages are therefore not context free. For example, once you have user defined types (very common in modern languages) you are automatically context sensitive.

There is a difference between verifying syntax and verifying semantic correctness of a program. Checking syntax is context free, whereas checking semantic correctness isn't (again, in most languages).

This, however, does not mean that such a language cannot exist. Untyped lambda calculus, for example, can be described using a context free grammar, and is, of course, Turing complete.

---

Most of the modern programming languages are not context-free languages. As a proof, if I delve into the root of CFL its corresponding machine PDA can't process string matchings like {ww | w is a string}. So most programming languages require that.

Example:

int fa; // w
fa=1; // ww as parser treat it like this

---

VHDL is somewhat context sensitive:

VHDL is context-sensitive in a mean way. Consider this statement inside a process:

jinx := foo(1);

Well, depending on the objects defined in the scope of the process (and its enclosing scopes), this can be either:

• A function call
• Indexing an array
• Indexing an array returned by a parameter-less function call

To parse this correctly, a parser has to carry a hierarchical symbol table (with enclosing scopes), and the current file isn't even enough. foo can be a function defined in a package. So the parser should first analyze the packages imported by the file it's parsing, and figure out the symbols defined in them.

This is just an example. The VHDL type/subtype system is a similarly context-sensitive mess that's very difficult to parse.

(Eli Bendersky, “Parsing VHDL is [very] hard”, 2009)

---

I think Haskell and ML are supporting context free. See this link for Haskell.

참고URL : https://stackoverflow.com/questions/898489/what-programming-languages-are-context-free