lexer.go 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802
  1. /*
  2. * ECAL
  3. *
  4. * Copyright 2020 Matthias Ladkau. All rights reserved.
  5. *
  6. * This Source Code Form is subject to the terms of the MIT
  7. * License, If a copy of the MIT License was not distributed with this
  8. * file, You can obtain one at https://opensource.org/licenses/MIT.
  9. */
  10. package parser
  11. import (
  12. "bytes"
  13. "encoding/json"
  14. "fmt"
  15. "regexp"
  16. "strconv"
  17. "strings"
  18. "unicode"
  19. "unicode/utf8"
  20. )
  21. /*
  22. NamePattern is the pattern for valid names.
  23. */
  24. var NamePattern = regexp.MustCompile("^[A-Za-z][A-Za-z0-9]*$")
  25. /*
  26. numberPattern is a hint pattern for numbers.
  27. */
  28. var numberPattern = regexp.MustCompile("^[0-9].*$")
  29. /*
  30. LexToken represents a token which is returned by the lexer.
  31. */
  32. type LexToken struct {
  33. ID LexTokenID // Token kind
  34. Pos int // Starting position (in bytes)
  35. Val string // Token value
  36. Identifier bool // Flag if the value is an identifier (not quoted and not a number)
  37. AllowEscapes bool // Flag if the value did interpret escape charaters
  38. PrefixNewlines int // Number of newlines which precede this token
  39. Lsource string // Input source label (e.g. filename)
  40. Lline int // Line in the input this token appears
  41. Lpos int // Position in the input line this token appears
  42. }
  43. /*
  44. NewLexTokenInstance creates a new LexToken object instance from given LexToken values.
  45. */
  46. func NewLexTokenInstance(t LexToken) *LexToken {
  47. return &LexToken{
  48. t.ID,
  49. t.Pos,
  50. t.Val,
  51. t.Identifier,
  52. t.AllowEscapes,
  53. t.PrefixNewlines,
  54. t.Lsource,
  55. t.Lline,
  56. t.Lpos,
  57. }
  58. }
  59. /*
  60. Equals checks if this LexToken equals another LexToken. Returns also a message describing
  61. what is the found difference.
  62. */
  63. func (t LexToken) Equals(other LexToken, ignorePosition bool) (bool, string) {
  64. var res = true
  65. var msg = ""
  66. if t.ID != other.ID {
  67. res = false
  68. msg += fmt.Sprintf("ID is different %v vs %v\n", t.ID, other.ID)
  69. }
  70. if !ignorePosition && t.Pos != other.Pos {
  71. res = false
  72. msg += fmt.Sprintf("Pos is different %v vs %v\n", t.Pos, other.Pos)
  73. }
  74. if t.Val != other.Val {
  75. res = false
  76. msg += fmt.Sprintf("Val is different %v vs %v\n", t.Val, other.Val)
  77. }
  78. if t.Identifier != other.Identifier {
  79. res = false
  80. msg += fmt.Sprintf("Identifier is different %v vs %v\n", t.Identifier, other.Identifier)
  81. }
  82. if !ignorePosition && t.Lline != other.Lline {
  83. res = false
  84. msg += fmt.Sprintf("Lline is different %v vs %v\n", t.Lline, other.Lline)
  85. }
  86. if !ignorePosition && t.Lpos != other.Lpos {
  87. res = false
  88. msg += fmt.Sprintf("Lpos is different %v vs %v\n", t.Lpos, other.Lpos)
  89. }
  90. if msg != "" {
  91. var buf bytes.Buffer
  92. out, _ := json.MarshalIndent(t, "", " ")
  93. buf.WriteString(string(out))
  94. buf.WriteString("\nvs\n")
  95. out, _ = json.MarshalIndent(other, "", " ")
  96. buf.WriteString(string(out))
  97. msg = fmt.Sprintf("%v%v", msg, buf.String())
  98. }
  99. return res, msg
  100. }
  101. /*
  102. PosString returns the position of this token in the origianl input as a string.
  103. */
  104. func (t LexToken) PosString() string {
  105. return fmt.Sprintf("Line %v, Pos %v", t.Lline, t.Lpos)
  106. }
  107. /*
  108. String returns a string representation of a token.
  109. */
  110. func (t LexToken) String() string {
  111. prefix := ""
  112. if !t.Identifier {
  113. prefix = "v:" // Value is not an identifier
  114. }
  115. switch {
  116. case t.ID == TokenEOF:
  117. return "EOF"
  118. case t.ID == TokenError:
  119. return fmt.Sprintf("Error: %s (%s)", t.Val, t.PosString())
  120. case t.ID == TokenPRECOMMENT:
  121. return fmt.Sprintf("/* %s */", t.Val)
  122. case t.ID == TokenPOSTCOMMENT:
  123. return fmt.Sprintf("# %s", t.Val)
  124. case t.ID > TOKENodeSYMBOLS && t.ID < TOKENodeKEYWORDS:
  125. return fmt.Sprintf("%s", strings.ToUpper(t.Val))
  126. case t.ID > TOKENodeKEYWORDS:
  127. return fmt.Sprintf("<%s>", strings.ToUpper(t.Val))
  128. case len(t.Val) > 20:
  129. // Special case for very long values
  130. return fmt.Sprintf("%s%.10q...", prefix, t.Val)
  131. }
  132. return fmt.Sprintf("%s%q", prefix, t.Val)
  133. }
  134. // Meta data interface
  135. /*
  136. Type returns the meta data type.
  137. */
  138. func (t LexToken) Type() string {
  139. if t.ID == TokenPRECOMMENT {
  140. return MetaDataPreComment
  141. } else if t.ID == TokenPOSTCOMMENT {
  142. return MetaDataPostComment
  143. }
  144. return MetaDataGeneral
  145. }
  146. /*
  147. Value returns the meta data value.
  148. */
  149. func (t LexToken) Value() string {
  150. return t.Val
  151. }
  152. /*
  153. KeywordMap is a map of keywords - these require spaces between them
  154. */
  155. var KeywordMap = map[string]LexTokenID{
  156. // Assign statement
  157. "let": TokenLET,
  158. // Import statement
  159. "import": TokenIMPORT,
  160. "as": TokenAS,
  161. // Sink definition
  162. "sink": TokenSINK,
  163. "kindmatch": TokenKINDMATCH,
  164. "scopematch": TokenSCOPEMATCH,
  165. "statematch": TokenSTATEMATCH,
  166. "priority": TokenPRIORITY,
  167. "suppresses": TokenSUPPRESSES,
  168. // Function definition
  169. "func": TokenFUNC,
  170. "return": TokenRETURN,
  171. // Boolean operators
  172. "and": TokenAND,
  173. "or": TokenOR,
  174. "not": TokenNOT,
  175. // String operators
  176. "like": TokenLIKE,
  177. "hasprefix": TokenHASPREFIX,
  178. "hassuffix": TokenHASSUFFIX,
  179. // List operators
  180. "in": TokenIN,
  181. "notin": TokenNOTIN,
  182. // Constant terminals
  183. "false": TokenFALSE,
  184. "true": TokenTRUE,
  185. "null": TokenNULL,
  186. // Conditional statements
  187. "if": TokenIF,
  188. "elif": TokenELIF,
  189. "else": TokenELSE,
  190. // Loop statements
  191. "for": TokenFOR,
  192. "break": TokenBREAK,
  193. "continue": TokenCONTINUE,
  194. // Try block
  195. "try": TokenTRY,
  196. "except": TokenEXCEPT,
  197. "otherwise": TokenOTHERWISE,
  198. "finally": TokenFINALLY,
  199. // Mutex block
  200. "mutex": TokenMUTEX,
  201. }
  202. /*
  203. SymbolMap is a map of special symbols which will always be unique - these will separate unquoted strings
  204. Symbols can be maximal 2 characters long.
  205. */
  206. var SymbolMap = map[string]LexTokenID{
  207. // Condition operators
  208. ">=": TokenGEQ,
  209. "<=": TokenLEQ,
  210. "!=": TokenNEQ,
  211. "==": TokenEQ,
  212. ">": TokenGT,
  213. "<": TokenLT,
  214. // Grouping symbols
  215. "(": TokenLPAREN,
  216. ")": TokenRPAREN,
  217. "[": TokenLBRACK,
  218. "]": TokenRBRACK,
  219. "{": TokenLBRACE,
  220. "}": TokenRBRACE,
  221. // Separators
  222. ".": TokenDOT,
  223. ",": TokenCOMMA,
  224. ";": TokenSEMICOLON,
  225. // Grouping
  226. ":": TokenCOLON,
  227. "=": TokenEQUAL,
  228. // Arithmetic operators
  229. "+": TokenPLUS,
  230. "-": TokenMINUS,
  231. "*": TokenTIMES,
  232. "/": TokenDIV,
  233. "//": TokenDIVINT,
  234. "%": TokenMODINT,
  235. // Assignment statement
  236. ":=": TokenASSIGN,
  237. }
  238. // Lexer
  239. // =====
  240. /*
  241. RuneEOF is a special rune which represents the end of the input
  242. */
  243. const RuneEOF = -1
  244. /*
  245. Function which represents the current state of the lexer and returns the next state
  246. */
  247. type lexFunc func(*lexer) lexFunc
  248. /*
  249. Lexer data structure
  250. */
  251. type lexer struct {
  252. name string // Name to identify the input
  253. input string // Input string of the lexer
  254. pos int // Current rune pointer
  255. line int // Current line pointer
  256. lastnl int // Last newline position
  257. skippedNewline int // Number of skipped newlines
  258. width int // Width of last rune
  259. start int // Start position of the current red token
  260. tokens chan LexToken // Channel for lexer output
  261. }
  262. /*
  263. Lex lexes a given input. Returns a channel which contains tokens.
  264. */
  265. func Lex(name string, input string) chan LexToken {
  266. l := &lexer{name, input, 0, 0, 0, 0, 0, 0, make(chan LexToken)}
  267. go l.run()
  268. return l.tokens
  269. }
  270. /*
  271. LexToList lexes a given input. Returns a list of tokens.
  272. */
  273. func LexToList(name string, input string) []LexToken {
  274. var tokens []LexToken
  275. for t := range Lex(name, input) {
  276. tokens = append(tokens, t)
  277. }
  278. return tokens
  279. }
  280. /*
  281. Main loop of the lexer.
  282. */
  283. func (l *lexer) run() {
  284. if skipWhiteSpace(l) {
  285. for state := lexToken; state != nil; {
  286. state = state(l)
  287. if !skipWhiteSpace(l) {
  288. break
  289. }
  290. }
  291. }
  292. close(l.tokens)
  293. }
  294. /*
  295. next returns the next rune in the input and advances the current rune pointer
  296. if peek is 0. If peek is >0 then the nth character is returned without advancing
  297. the rune pointer.
  298. */
  299. func (l *lexer) next(peek int) rune {
  300. // Check if we reached the end
  301. if int(l.pos) >= len(l.input) {
  302. return RuneEOF
  303. }
  304. // Decode the next rune
  305. pos := l.pos
  306. if peek > 0 {
  307. pos += peek - 1
  308. }
  309. r, w := utf8.DecodeRuneInString(l.input[pos:])
  310. if peek == 0 {
  311. l.width = w
  312. l.pos += l.width
  313. }
  314. return r
  315. }
  316. /*
  317. backup sets the pointer one rune back. Can only be called once per next call.
  318. */
  319. func (l *lexer) backup(width int) {
  320. if width == 0 {
  321. width = l.width
  322. }
  323. l.pos -= width
  324. }
  325. /*
  326. startNew starts a new token.
  327. */
  328. func (l *lexer) startNew() {
  329. l.start = l.pos
  330. }
  331. /*
  332. emitToken passes a token back to the client.
  333. */
  334. func (l *lexer) emitToken(t LexTokenID) {
  335. if t == TokenEOF {
  336. l.emitTokenAndValue(t, "", false, false)
  337. return
  338. }
  339. if l.tokens != nil {
  340. l.tokens <- LexToken{t, l.start, l.input[l.start:l.pos], false, false, l.skippedNewline, l.name,
  341. l.line + 1, l.start - l.lastnl + 1}
  342. }
  343. }
  344. /*
  345. emitTokenAndValue passes a token with a given value back to the client.
  346. */
  347. func (l *lexer) emitTokenAndValue(t LexTokenID, val string, identifier bool, allowEscapes bool) {
  348. if l.tokens != nil {
  349. l.tokens <- LexToken{t, l.start, val, identifier, allowEscapes, l.skippedNewline,
  350. l.name, l.line + 1, l.start - l.lastnl + 1}
  351. }
  352. }
  353. /*
  354. emitError passes an error token back to the client.
  355. */
  356. func (l *lexer) emitError(msg string) {
  357. if l.tokens != nil {
  358. l.tokens <- LexToken{TokenError, l.start, msg, false, false, l.skippedNewline,
  359. l.name, l.line + 1, l.start - l.lastnl + 1}
  360. }
  361. }
  362. // Helper functions
  363. // ================
  364. /*
  365. skipWhiteSpace skips any number of whitespace characters. Returns false if the parser
  366. reaches EOF while skipping whitespaces.
  367. */
  368. func skipWhiteSpace(l *lexer) bool {
  369. r := l.next(0)
  370. l.skippedNewline = 0
  371. for unicode.IsSpace(r) || unicode.IsControl(r) || r == RuneEOF {
  372. if r == '\n' {
  373. l.line++
  374. l.skippedNewline++
  375. l.lastnl = l.pos
  376. }
  377. r = l.next(0)
  378. if r == RuneEOF {
  379. l.emitToken(TokenEOF)
  380. return false
  381. }
  382. }
  383. l.backup(0)
  384. return true
  385. }
  386. /*
  387. lexTextBlock lexes a block of text without whitespaces. Interprets
  388. optionally all one or two letter tokens.
  389. */
  390. func lexTextBlock(l *lexer, interpretToken bool) {
  391. r := l.next(0)
  392. if interpretToken {
  393. // Check if we start with a known symbol
  394. nr := l.next(1)
  395. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  396. l.next(0)
  397. return
  398. }
  399. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  400. return
  401. }
  402. }
  403. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  404. if interpretToken {
  405. // Check if we find a token in the block
  406. if _, ok := SymbolMap[strings.ToLower(string(r))]; ok {
  407. l.backup(0)
  408. return
  409. }
  410. nr := l.next(1)
  411. if _, ok := SymbolMap[strings.ToLower(string(r)+string(nr))]; ok {
  412. l.backup(0)
  413. return
  414. }
  415. }
  416. r = l.next(0)
  417. }
  418. if r != RuneEOF {
  419. l.backup(0)
  420. }
  421. }
  422. /*
  423. lexNumberBlock lexes a block potentially containing a number.
  424. */
  425. func lexNumberBlock(l *lexer) {
  426. r := l.next(0)
  427. for !unicode.IsSpace(r) && !unicode.IsControl(r) && r != RuneEOF {
  428. if !unicode.IsNumber(r) && r != '.' {
  429. if r == 'e' {
  430. l1 := l.next(1)
  431. l2 := l.next(2)
  432. if l1 != '+' || !unicode.IsNumber(l2) {
  433. break
  434. }
  435. l.next(0)
  436. l.next(0)
  437. } else {
  438. break
  439. }
  440. }
  441. r = l.next(0)
  442. }
  443. if r != RuneEOF {
  444. l.backup(0)
  445. }
  446. }
  447. // State functions
  448. // ===============
  449. /*
  450. lexToken is the main entry function for the lexer.
  451. */
  452. func lexToken(l *lexer) lexFunc {
  453. // Check if we got a quoted value or a comment
  454. n1 := l.next(1)
  455. n2 := l.next(2)
  456. // Parse comments
  457. if (n1 == '/' && n2 == '*') || n1 == '#' {
  458. return lexComment
  459. }
  460. // Parse strings
  461. if (n1 == '"' || n1 == '\'') || (n1 == 'r' && (n2 == '"' || n2 == '\'')) {
  462. return lexValue
  463. }
  464. // Lex a block of text and emit any found tokens
  465. l.startNew()
  466. // First try to parse a number
  467. lexNumberBlock(l)
  468. identifierCandidate := l.input[l.start:l.pos]
  469. keywordCandidate := strings.ToLower(identifierCandidate)
  470. // Check for number
  471. if numberPattern.MatchString(keywordCandidate) {
  472. _, err := strconv.ParseFloat(keywordCandidate, 64)
  473. if err == nil {
  474. l.emitTokenAndValue(TokenNUMBER, keywordCandidate, false, false)
  475. return lexToken
  476. }
  477. }
  478. if len(keywordCandidate) > 0 {
  479. l.backup(l.pos - l.start)
  480. }
  481. lexTextBlock(l, true)
  482. identifierCandidate = l.input[l.start:l.pos]
  483. keywordCandidate = strings.ToLower(identifierCandidate)
  484. // Check for keyword
  485. token, ok := KeywordMap[keywordCandidate]
  486. if !ok {
  487. // Check for symbol
  488. token, ok = SymbolMap[keywordCandidate]
  489. }
  490. if ok {
  491. // A known token was found
  492. l.emitToken(token)
  493. } else {
  494. if !NamePattern.MatchString(keywordCandidate) {
  495. l.emitError(fmt.Sprintf("Cannot parse identifier '%v'. Identifies may only contain [a-zA-Z] and [a-zA-Z0-9] from the second character", keywordCandidate))
  496. return nil
  497. }
  498. // An identifier was found
  499. l.emitTokenAndValue(TokenIDENTIFIER, identifierCandidate, true, false)
  500. }
  501. return lexToken
  502. }
  503. /*
  504. lexValue lexes a string value.
  505. Values can be declared in different ways:
  506. ' ... ' or " ... "
  507. Characters are parsed between quotes (escape sequences are interpreted)
  508. r' ... ' or r" ... "
  509. Characters are parsed plain between quote
  510. */
  511. func lexValue(l *lexer) lexFunc {
  512. var endToken rune
  513. l.startNew()
  514. allowEscapes := false
  515. r := l.next(0)
  516. // Check if we have a raw quoted string
  517. if q := l.next(1); r == 'r' && (q == '"' || q == '\'') {
  518. endToken = q
  519. l.next(0)
  520. } else {
  521. allowEscapes = true
  522. endToken = r
  523. }
  524. r = l.next(0)
  525. rprev := ' '
  526. lLine := l.line
  527. lLastnl := l.lastnl
  528. for (!allowEscapes && r != endToken) ||
  529. (allowEscapes && (r != endToken || rprev == '\\')) {
  530. if r == '\n' {
  531. lLine++
  532. lLastnl = l.pos
  533. }
  534. rprev = r
  535. r = l.next(0)
  536. if r == RuneEOF {
  537. l.emitError("Unexpected end while reading string value (unclosed quotes)")
  538. return nil
  539. }
  540. }
  541. if allowEscapes {
  542. val := l.input[l.start+1 : l.pos-1]
  543. // Interpret escape sequences right away
  544. if endToken == '\'' {
  545. // Escape double quotes in a single quoted string
  546. val = strings.Replace(val, "\"", "\\\"", -1)
  547. }
  548. s, err := strconv.Unquote("\"" + val + "\"")
  549. if err != nil {
  550. l.emitError(err.Error() + " while parsing string")
  551. return nil
  552. }
  553. l.emitTokenAndValue(TokenSTRING, s, false, true)
  554. } else {
  555. l.emitTokenAndValue(TokenSTRING, l.input[l.start+2:l.pos-1], false, false)
  556. }
  557. // Set newline
  558. l.line = lLine
  559. l.lastnl = lLastnl
  560. return lexToken
  561. }
  562. /*
  563. lexComment lexes comments.
  564. */
  565. func lexComment(l *lexer) lexFunc {
  566. // Consume initial /*
  567. r := l.next(0)
  568. if r == '#' {
  569. l.startNew()
  570. for r != '\n' && r != RuneEOF {
  571. r = l.next(0)
  572. }
  573. l.emitTokenAndValue(TokenPOSTCOMMENT, l.input[l.start:l.pos], false, false)
  574. if r == RuneEOF {
  575. return nil
  576. }
  577. l.line++
  578. } else {
  579. l.next(0)
  580. lLine := l.line
  581. lLastnl := l.lastnl
  582. l.startNew()
  583. r = l.next(0)
  584. for r != '*' || l.next(1) != '/' {
  585. if r == '\n' {
  586. lLine++
  587. lLastnl = l.pos
  588. }
  589. r = l.next(0)
  590. if r == RuneEOF {
  591. l.emitError("Unexpected end while reading comment")
  592. return nil
  593. }
  594. }
  595. l.emitTokenAndValue(TokenPRECOMMENT, l.input[l.start:l.pos-1], false, false)
  596. // Consume final /
  597. l.next(0)
  598. // Set newline
  599. l.line = lLine
  600. l.lastnl = lLastnl
  601. }
  602. return lexToken
  603. }