정규 언어 표현을 사용하는 것이 편리합니다 (제 경우에는 도메인 특정 언어). 그러나 표준 언어가 그 언어로 된 임의의 프로그램에 대해 결정 및/또는 생성 될 수 있는지 여부를 결정하는 데 관련된 언어의 표현력에 엄격한 제한이 있다고 생각합니다. 불행히도, 나는 이것을 막연하게 읽었던 참고 문헌을 찾을 수 없었다.정규 언어 표현을 작성하는 일반적인 복잡성은 무엇입니까?
한편으로는 언어의 표준 표현을 만드는 것이 많은 하드 그래프 문제에 필적 할만큼 복잡하다. (eg : 그래프 동형 성), 반면에 iirc, gcc, yhc, ghc와 같은 컴파일러는 다양한 형식 (어셈블리, 자바 스크립트 등)으로 출력을 생성하기 위해 중간 표현을 사용하므로, 해결 된 문제.
때 주어진 언어에 대한 표준 형식/결정 생성 할 수있다? (언어 표현력은 얼마나 표현력이 있습니까? 그리고 언어 표현력이 표준 형식의 유용성에 어떻게 영향을 줍니까?) 가능하다면 참고 문헌이나 교정본을 제공해주십시오.
편집 : 예를 들어하는 Regular Language (예 : 정규 표현식의 '순수한'형태)는 Turing-complete language 캔 같은 많은 일들을 표현할 수 없습니다. 다른 말로하면 정규 언어로 웹 서버를 작성할 수는 없지만 람다 미적분을 사용하면됩니다. 제 질문은 이론적 인 가능성에 관한 것이며 복잡한 이론과 관련된 구체적인 대답을 가지고 있습니다. DSL을 다른 시스템으로 전송해야하는 경우 DSL을 전송하기 전에 정식 형식을 생성하는 것이 유리합니다. 두 가지 시스템에서 사용되는 독립적 인 표현을 분리 할 것이기 때문입니다. 그러나 인 경우, P-Space가 완료되었거나 Turing-complete 언어를 표준 형식으로 변환하려면 NP-Complete이면 정규 형식을 작성하는 데 시간을 낭비하지 않아야합니다. , 또는 언어 복잡성을 이 될 수있는 것으로을 다항식 시간으로 정규화 할 수 있습니다.
여기에 맞춤법이 아닌 나치가 되려고하지만, 단 하나의 명사로 작성된 것은 아닙니다. "정식"? ;) – Mecki
이 질문은 답을 얻기에는 너무 힘들다고 판단됩니다. 나는 모든 단어의 뜻을 알고 있지만, 당신이 무엇을 요구하고 있는지 정말로 확신하지 못합니다. – Marcin
@Mecki 감사합니다! 오타가 수정되었습니다. – rcreswick